P4396
题意：给定一个序列，m个询问，每次询问给定一个区间 [ l , r ] 和两个数 a b ，求这个区间中有多少数在 [ a , b ] 区间之间和有多少数出现在 [ a , b ] 之间。 文字可能表述不好，下面给一组样例： 序列 1 2 2 询问 1 3 1 3 ( l , r , a , b ) 答案 3 2
最近学莫队肯定是用莫队来搞了，显然 [ a , b ] 可以转换成前缀来搞，用两个树状数组来维护就行了，一个直接维护前缀个数，一个维护当前数是否出现即可。 时间复杂度： O ( N N l o g N ) O(N\sqrt{N}logN) O(NN logN)
正解应该是套上值域分块(奈何我目前不会啊。
#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define pb push_back #define mk make_pair #define lowbit(x) (x)&(-x) using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6; int n,m; int ans1[N],ans2[N],id[N],tr1[N],tr2[N],a[N],cnt[N]; struct Node { int l,r,a,b; int id; }q[N]; bool cmp(Node a,Node b) { return id[a.l]^id[b.l]? a.l<b.l : ((id[a.l]&1)? a.r<b.r : a.r>b.r); } void ad1(int x,int y) { for(int i=x;i<=n;i+=lowbit(i)) tr1[i]+=y; } void ad2(int x,int y) { for(int i=x;i<=n;i+=lowbit(i)) tr2[i]+=y; } int sum1(int x) { int ans=0; for(int i=x;i;i-=lowbit(i)) ans+=tr1[i]; return ans; } int sum2(int x) { int ans=0; for(int i=x;i;i-=lowbit(i)) ans+=tr2[i]; return ans; } void add(int x) { x=a[x]; ad1(x,1); if(!cnt[x]) ad2(x,1); cnt[x]++; } void del(int x) { x=a[x]; ad1(x,-1); cnt[x]--; if(!cnt[x]) ad2(x,-1); } int main() { // ios::sync_with_stdio(false); // cin.tie(0); scanf("%d%d",&n,&m); int se=sqrt(n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); id[i]=(i-1)/se+1; } for(int i=1;i<=m;i++) scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b),q[i].id=i; sort(q+1,q+1+m,cmp); int l=1,r=0; for(int i=1;i<=m;i++) { int lx=q[i].l,rx=q[i].r; int a=q[i].a,b=q[i].b; while(l<lx) del(l++); while(l>lx) add(--l); while(r<rx) add(++r); while(r>rx) del(r--); int x,y,z,w; x=sum1(a-1),y=sum1(b); z=sum2(a-1),w=sum2(b); ans1[q[i].id]=y-x; ans2[q[i].id]=w-z; } for(int i=1;i<=m;i++) printf("%d %d\n",ans1[i],ans2[i]); return 0; } /* */