題目鏈接：點擊查看

題目大意：在二維平面內有 $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?\sqrt{n}?1+n?1?\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(莫队+树状数组/值域分块)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。