2025年2021hdu多校1 zoto（莫队+值域分块）

科技前沿 • 2025-03-10 09:56 • 阅读 44

大家好，我是讯享网，很高兴认识大家。

题目链接

题意

在坐标系中，对于1到n每个横坐标，给出其纵坐标的值，有q次询问，每次给出一个矩形的左下角和右上角，问矩形覆盖的点的不同纵坐标的数量。

思路

对于没有修改操作的区间查询问题，可以观察一下莫队是否可行，若没有对纵坐标的限制，仅问横坐标区间的点的不同纵坐标的数量，可直接用莫队；

讯享网

但现在加上纵坐标的限制，就要思考一下如何维护，观察到，如果先按普通莫队进行操作，确定出横坐标区间[x0,x1]的不同纵坐标的数量，取纵坐标位于[y0,y1]的不同纵坐标的数量即可；对于每一个纵坐标y值，若数量大于0，则设为1,等于0，设为0，放入树状数组/线段树中即可维护。修改O(logn)，查询O(logn)，可能会超时（没试过。。。）。

因为纵坐标y值小于等于1e5，可以考虑值域分块，对y值进行分块，可做到修改O(1),查询O(√n)，但在本题中修改次数多于查询次数，总时间复杂度为O(n√n+m√n)。

代码

//莫队+值域分块 //#pragma GCC optimize(2) #include <bits/stdc++.h> using namespace std; typedef long long ll; struct node{ int l,r,x,y,id; }q[]; int siz; int a[]; int ans[]; int pos[]; int cnt[]; int t1[10010]; int t2[]; void add(int x){ cnt[a[x]]++; if(cnt[a[x]]==1){ t1[a[x]/siz]++; t2[a[x]]++; } } void sub(int x){ cnt[a[x]]--; if(!cnt[a[x]]){ t1[a[x]/siz]--; t2[a[x]]--; } } int sum(int x){ int i,ans=0; for(i=0;(i+1)*siz<=x;i++) ans+=t1[i]; for(i=i*siz;i<=x;i++) ans+=t2[i]; return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m; int _; cin>>_; while(_--){ memset(t1,0,sizeof(t1)); memset(t2,0,sizeof(t2)); memset(cnt,0,sizeof(cnt)); cin>>n>>m; siz=sqrt(n); for(int i=1;i<=n;i++){ cin>>a[i]; a[i]++; pos[i]=i/siz; } for(int i=1;i<=m;i++){ cin>>q[i].l>>q[i].x>>q[i].r>>q[i].y; q[i].x++; q[i].y++; q[i].id=i; } sort(q+1,q+m+1,[](node a,node b){ return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.l]&1)?a.r<b.r:a.r>b.r); }); int l=1,r=0; for(int i=1;i<=m;i++){ while(q[i].l<l) add(--l); while(q[i].r>r) add(++r); while(q[i].l>l) sub(l++); while(q[i].r<r) sub(r--); ans[q[i].id]=sum(q[i].y)-sum(q[i].x-1); } for(int i=1;i<=m;i++) cout<<ans[i]<<"\n"; } return 0; }

讯享网

几个相似的题

Gty的二逼妹子序列
[AHOI2013]作业

2025年2021hdu多校1 zoto（莫队+值域分块）

题意

思路

代码

几个相似的题

相关推荐