bzoj 3809 Gty的二逼妹子序列

bzoj 3809 Gty的二逼妹子序列

题目

一个n个元素的数组，元素大小∈[1,n]，每次询问[l,r]中，数值[s,t]中出现了多少种
n<=1e5,m<=1e6

题解

比较容易发现的做法是莫队然后用树状数组维护
这样复杂度就是 O ( n m l o g n ) O(nsqrt mlogn) O(nm ​logn)的
于是应该就T了
其实我还专门交了发试试，确实T了…
关注到n和m不同
我们分析一下需要的操作
1.插入&删除 O ( n m ) O(nsqrt m) O(nm ​)次
2.查询 O ( m ) O(m) O(m)次
之前我们用树状数组维护的话这些都是logn的
我们考虑牺牲2的复杂度来降低1的复杂度：分块
我们用分块来维护值域，那么插入就成了 O ( 1 ) O(1) O(1)，查询就成了 O ( n ) O(sqrt n) O(n ​)
也就是说复杂度变成了 O ( n m + m n ) O(nsqrt m+msqrt n) O(nm ​+mn ​)
内存限制丧心病狂…

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=100005,M=1000005;
struct node{int l,r,s,t,pos;
}q[M];
int a[N];
int block[N];
bool cmp(node a,node b){if(block[a.l]!=block[b.l])return block[a.l]<block[b.l];return a.r<b.r;
}
int cnt[N];
int sum[N];
void Add(int x){if(cnt[x]==0){sum[block[x]]++;}cnt[x]++;
}
void Delete(int x){cnt[x]--;if(cnt[x]==0)sum[block[x]]--;
}
int Query(int x,int y){int res=0;if(block[y]-block[x]<=1){for(int i=x;i<=y;i++)res+=cnt[i]>0;return res;}for(int i=block[x]+1;i<=block[y]-1;i++)res+=sum[i];for(int i=x;block[i]==block[x];i++)res+=cnt[i]>0;for(int i=y;block[i]==block[y];i--)res+=cnt[i]>0;return res;
}
int n,m;
int ans[M];
void Read(int &x){x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
}
int main()
{Read(n),Read(m);//scanf("%d%d",&n,&m);int S=sqrt(n);for(int i=1;i<=n;i++)block[i]=(i-1)/S+1;for(int i=1;i<=n;i++){Read(a[i]);//scanf("%d",&a[i]);}for(int i=1;i<=m;i++){Read(q[i].l),Read(q[i].r),Read(q[i].s),Read(q[i].t);//scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].s,&q[i].t);q[i].pos=i;}sort(q+1,q+m+1,cmp);int l=1,r=0;for(int i=1;i<=m;i++){int ql=q[i].l,qr=q[i].r;while(l>ql){l--;Add(a[l]);}while(r<qr){r++;Add(a[r]);}while(l<ql){Delete(a[l]);l++;}while(r>qr){Delete(a[r]);r--;}ans[q[i].pos]=Query(q[i].s,q[i].t);}for(int i=1;i<=m;i++)printf("%dn",ans[i]);
}