题目：点击此处
题意：给你n个数，q个询问，问每个区间的数最少需要几步可以删除完
删除的是一个等差序列
由于第一次删除之后，剩下的数字随机排列，所以，只要第一次删除可以把一种数字全部删除，剩下的步数就是数字种类数
总步数即为 总的种类数
如果一次删不完一种数，那么答案就是总的种类数+1
判断是否是等差序列需要预处理 两个数组 fl[N],fr[N];
fl[i]表示i位置往左第一个构不成等差序列的位置
fr[i]同理；
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <set> #include <vector> #include <iostream> using namespace std; const int N=100005; struct node { int x,y,p; }q[N]; bool cmp(node a,node b) { if (a.x/block!=b.x/block) return a.x/block<b.x/block; return a.y<b.y; } int aa[N]; int bak[N]; int pre[N]; int last[N]; int fl[N],fr[N]; int cnt[N]; int dengcha=0; int kind=0; int ans[N]; int L,R,block=sqrt(N); void add1(int x) { if(cnt[aa[x]]==0) { dengcha++; kind++; } else { if(fr[x]<=R&&fr[bak[x]]>R) dengcha--; } cnt[aa[x]]++; } void remov1e(int x) { if(cnt[aa[x]]==1) { dengcha--; kind--; } else { if(fr[x]<=R&&fr[bak[x]]>R) dengcha++; } cnt[aa[x]]--; } void add2(int x,int l) { if(cnt[aa[x]]==0) { dengcha++; kind++; } else { if(fl[x]>=l&&fl[pre[x]]<l) dengcha--; } cnt[aa[x]]++; } void remov2e(int x,int l) { if(cnt[aa[x]]==1) { dengcha--; kind--; } else { if(fl[x]>=l&&fl[pre[x]]<l) dengcha++; } cnt[aa[x]]--; } void query(int x,int y,int flag) { if (flag) { while(L>=x) { add1(L-1); L--; } while(L<x) { remov1e(L); L++; } while(R>y) { remov2e(R,x); R--; } while(R<y) { add2(R+1,x); R++; } } else { for (int i=x;i<=y;i++) { if(cnt[aa[i]]==0) { dengcha++; kind++; } else { if (fl[i]>=x&&fl[pre[i]]<x) dengcha--;//fl[i]>=x 指 i位置往左第一个构不成等差序列的位置在区间内， fl[pre[i]]<x 指 pre[i]位置往左第一个构不成等差序列的位置不在区间内，（防止重复计算） } cnt[aa[i]]++; } L=x,R=y; } } void init() { int i; kind = 0; for (i=1; i<=m; i++) //预处理 { scanf("%d",&aa[i]); pre[i]=last[aa[i]]; last[aa[i]]=i; if (pre[pre[i]]-pre[i]==pre[i]-i||pre[i]==0) fl[i]=fl[pre[i]]; else fl[i]=pre[pre[i]]; } fill(last,m+last,m+1); for (i=m; i>=1; i--) { bak[i]=last[aa[i]]; last[aa[i]]=i; if (bak[bak[i]]-bak[i]==bak[i]-i||bak[i]==m+1) fr[i]=fr[bak[i]]; else fr[i]=bak[bak[i]]; } } int main() { int m,i,j,qq,; cin>>m; init(); scanf("%d",&qq); for (i=0;i<qq; i++) { scanf("%d%d",&q[i].x,&q[i].y); q[i].l=q[i].x/block_size; q[i].p=i; } sort(q,q+qq,cmp); for (i=0;i<qq;i++) { query(q[i].x,q[i].y, i); ans[q[i].p]=kind+1; if (dengcha>0) ans[q[i].p]--; } for (i=0;i<qq;i++) printf("%d\n",ans[i]); return 0; }
