题目 输入样例#1： 10 10 4 4 5 1 4 1 5 1 2 1 5 9 1 2 3 4 7 9 4 4 2 5 2 3 4 7 5 10 4 4 3 9 1 1 1 4 5 9 8 9 3 3 2 2 1 6 8 9 1 4
输出样例#1： 2 0 0 2 1 1 1 0 1 2
【样例的部分解释】 5 9 1 2 子序列为4 1 5 1 2 在[1,2]里的权值有1,1,2，有2种，因此答案为2。 3 4 7 9 子序列为5 1 在[7,9]里的权值有5，有1种，因此答案为1。 4 4 2 5 子序列为1 没有权值在[2,5]中的，因此答案为0。 2 3 4 7 子序列为4 5 权值在[4,7]中的有4,5，因此答案为2。 建议使用输入/输出优化。
思路：这个题很显然可以用莫队+树状数组+vis[]标记解决。
add:x=a[x];vis[x]++;if(vis[x]==1) modify(x,1). del:x=a[x];vis[x]--;if(!vis[x]) modify(x,-1). query(l,r):if(l!=1) return getsum(r)-getsum(l-1); else return getsum(r);modify的复杂度log(n)。每次dexl,dexr移动次数很多。但是query次数是m。 由于这个特性.我们可以采用分块。 还有block1=block2=sqrt(n) 。否则TLE。好玄好烦 而且我们这个统计可以全部移动完统计,不是很像以前那种，dexl,dexr移动期间就必须要求出对res的影响(否则移动完遍历复杂度会白白增大,不如边移动边更新res) (我也说不清)。 add,del：x=a[x];tag[x],sum[bl[x]]相应修改 query：零散+整块
//一开始是这样写的...一直WA(我脑子进水 我有病!!!) void change(int x,int val) { tag[x]+=val; if(tag[x]==1)//这个等于1不是啊 我mmp???(改成val==1&&tag[x]==1)就AC. sum[bl[x]]++; if(!tag[x])//这个等于0时肯定是因为val=-1 sum[bl[x]]--; } void add(int x){ change(a[x],1); } void del(int x){ change(a[x],-1); } #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #define en '\n' #define foru(i,a,b) for(int i=a;i<=b;++i) #define m(a,b) memset(a,b,sizeof a) using namespace std; typedef long long ll; const int N=1e5+5,M=1e6+5,INF=0x3f3f3f3f; template<class T>void rd(T &x) { x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return; } int a[N]; int dexl,dexr; int ans[M]; struct Query{int id,l,r,u,v;}q[M]; int sum[320],tag[N],bl[N],block; bool cmp(Query x,Query y) { if(bl[x.l]==bl[y.l]) return x.r<y.r; return bl[x.l]<bl[y.l]; } int query(int l,int r) { int ans=0; for(int i=l;i<=min(bl[l]*block,r);i++) if(tag[i]) ++ans; if(bl[l]!=bl[r]) for(int i=(bl[r]-1)*block+1;i<=r;i++) if(tag[i]) ++ans; for(int i=bl[l]+1;i<=bl[r]-1;i++) ans+=sum[i]; return ans; } void add(int x) { x=a[x]; tag[x]++; if(tag[x]==1) sum[bl[x]]++; } void del(int x) { x=a[x]; tag[x]--; if(!tag[x]) sum[bl[x]]--; } int main() { //m(tag,0); int n,m;rd(n),rd(m);block=sqrt(n); foru(i,1,n) rd(a[i]),bl[i]=(i-1)/block+1; foru(i,1,m) rd(q[i].l),rd(q[i].r),rd(q[i].u),rd(q[i].v),q[i].id=i; sort(q+1,q+m+1,cmp); dexl=1,dexr=0; foru(i,1,m) { while(dexr<q[i].r) add(++dexr); while(dexl>q[i].l) add(--dexl); while(dexr>q[i].r) del(dexr--); while(dexl<q[i].l) del(dexl++); ans[q[i].id]=query(q[i].u,q[i].v); } foru(i,1,m) printf("%d\n",ans[i]); }