HDU多校1 - 6959 zoto(莫队+树状数组/值域分块)

题目链接：点击查看

题目大意：在二维平面内有 $n$ 个点，表示为 $(i,f[i])$，需要回答 $m$ 次询问，每次询问会给出一个矩形，问矩形内有多少个不同的 $y$ 值

题目分析：对于 $x$ 轴而言可以视为区间询问，每次询问的是“颜色”个数，因为可以离线，所以不难想到对 $x$ 轴套上莫队。莫队需要支持增加、删除和询问操作，对应到 $y$ 轴上也就是单点修改、区间查询，不难想到对 $y$ 轴套上树状数组。因为数据较水，所以到此就产生出了一种可以AC的做法，就是莫队套树状数组。莫队每次修改是 $O(\sqrt{n})$，查询是 $O(1)$，树状数组每次修改和查询都是 $O(logn)$，所以最终复杂度就是 $O(nlogn\sqrt{n})$ 的

但是题解给出了一种更优的解法，观察到上述解法的瓶颈在于莫队的修改是 $O(\sqrt{n})$ 的，我们如果将“单点修改、区间查询” 的单点修改的复杂度压缩到 $O(1)$，对于查询而言是可以做到 $O(\sqrt{n})$ 去查询的，也就是值域分块了。到此就会神奇的发现，总复杂度是 $O(n\ast \sqrt{n}\ast 1+n\ast 1\ast \sqrt{n})=O(n\sqrt{n})$ 了

代码：

莫队+值域分块：

// Problem: zoto // Contest: Virtual Judge - HDU // URL: https://vjudge.net/problem/HDU-6959 // Memory Limit: 131 MB // Time Limit: 2500 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e5+100; int size,n,m,ans[N],a[N],sum[N],cnt[N]; struct query {int l,r,id,x,y;bool operator<(const query& a)const{if(l/size!=a.l/size)return l<a.l;else if((l/size)&1)return r<a.r;elsereturn r>a.r;} }q[N]; int ask(int n) {int ans=0;for(int i=0;i<n/size;i++) {ans+=sum[i];}for(int i=(n/size)*size;i<=n;i++) {ans+=!!cnt[i];}return ans; } void del(int x) {cnt[a[x]]--;if(!cnt[a[x]]) {sum[a[x]/size]--;} } void add(int x) {if(!cnt[a[x]]) {sum[a[x]/size]++;}cnt[a[x]]++; } void solve() {int l=1,r=0;for(int i=1;i<=m;i++){int ql=q[i].l;int qr=q[i].r;while(l<ql) del(l++);while(l>ql) add(--l);while(r<qr) add(++r);while(r>qr) del(r--);ans[q[i].id]=ask(q[i].y)-ask(q[i].x-1);} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;size=313;while(w--) {memset(sum,0,sizeof(sum));memset(cnt,0,sizeof(cnt));read(n),read(m);for(int i=1;i<=n;i++) {read(a[i]);a[i]++;}for(int i=1;i<=m;i++) {read(q[i].l),read(q[i].x),read(q[i].r),read(q[i].y);q[i].x++,q[i].y++;q[i].id=i;}sort(q+1,q+1+m);solve();for(int i=1;i<=m;i++) {printf("%d\n",ans[i]);}}return 0; }

莫队+树状数组：

// Problem: zoto // Contest: Virtual Judge - HDU // URL: https://vjudge.net/problem/HDU-6959 // Memory Limit: 131 MB // Time Limit: 2500 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e5+100; int size,n,m,ans[N],a[N],c[N],cnt[N]; struct query {int l,r,id,x,y;bool operator<(const query& a)const{if(l/size!=a.l/size)return l<a.l;else if((l/size)&1)return r<a.r;elsereturn r>a.r;} }q[N]; void add(int x,int val) {for(int i=x;i<N;i+=lowbit(i)) {c[i]+=val;} } int ask(int x) {int ans=0;for(int i=x;i>0;i-=lowbit(i)) {ans+=c[i];}return ans; } void del(int x) {cnt[a[x]]--;if(!cnt[a[x]]) {add(a[x],-1);} } void add(int x) {if(!cnt[a[x]]) {add(a[x],1);}cnt[a[x]]++; } void solve() {int l=1,r=0;for(int i=1;i<=m;i++){int ql=q[i].l;int qr=q[i].r;while(l<ql) del(l++);while(l>ql) add(--l);while(r<qr) add(++r);while(r>qr) del(r--);ans[q[i].id]=ask(q[i].y)-ask(q[i].x-1);} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--) {memset(c,0,sizeof(c));memset(cnt,0,sizeof(cnt));read(n),read(m);size=sqrt(n);for(int i=1;i<=n;i++) {read(a[i]);a[i]++;}for(int i=1;i<=m;i++) {read(q[i].l),read(q[i].x),read(q[i].r),read(q[i].y);q[i].x++,q[i].y++;q[i].id=i;}sort(q+1,q+1+m);solve();for(int i=1;i<=m;i++) {printf("%d\n",ans[i]);}}return 0; }

总结

以上是生活随笔为你收集整理的HDU多校1 - 6959 zoto(莫队+树状数组/值域分块)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。