看到全是線段樹或者樹狀數(shù)組寫法，就來提供一發(fā)全網(wǎng)唯一cdq分治三維偏序解法吧

容易發(fā)現(xiàn)，這個題的查詢就是對于每個區(qū)間l,r，查詢有多少個修改區(qū)間l_i,r_i與l,r有交集

轉(zhuǎn)化為數(shù)學(xué)語言，就是查詢滿足l_i<=r且r_i>=l的修改個數(shù)

一個二維偏序問題，但是我們發(fā)現(xiàn)，這是個動態(tài)插入的二維偏序問題

_(:з」∠)_一時不知所措

再想一想，不妨把時間另開一個維度作為第三維，然后就是這樣了

對于每個查詢，我們要求出它之前有多少個修改區(qū)間與其相交

數(shù)學(xué)語言：

查詢滿足l_i<=r且r_i>=l且[l_i,r_i].time<[l,r].time的修改個數(shù)

思路清晰明了，而且敲好想，但是實現(xiàn)細節(jié)還是比較麻煩的（一部分是因為我的奇葩cdq寫法），在代碼注釋里解釋一下（模板這種的就不解釋了）

#include<iostream> #include<cstdio> #include<algorithm> #include<vector> using namespace std; const int maxn=1e5+10; struct node{int a,b,c,q,w; //a,b,c表示三個維度，q記錄這個操作是修改還是查詢 //w表示這個是否有效（和q差不多，查詢是不需要統(tǒng)計的，w=0；修改的w=1） }v[maxn]; int n,m,cnt,tot,c[maxn],ans[maxn]; bool vis[maxn]; bool cmpx(const node &a,const node &b) {return a.a==b.a?(a.b==b.b?a.c<b.c:a.b<b.b):a.a<b.a; } bool cmpy(const node &a,const node &b) {return a.b==b.b?a.c<b.c:a.b<b.b; } int lowbit(int x) {return x&-x; } void add(int x,int ch) {while(x<=n){c[x]+=ch;x+=lowbit(x);} } int sum(int x) {int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret; } void cdq(int l,int r) {if(l==r)return;int mid=l+r>>1;cdq(l,mid),cdq(mid+1,r);sort(v+l,v+mid+1,cmpy),sort(v+mid+1,v+r+1,cmpy);int i=l,j=mid+1;for(;j<=r;j++){while(v[i].b<=v[j].b&&i<=mid)add(v[i].c,v[i].w),i++;if(v[j].q==2)ans[v[j].a]+=sum(n)-sum(v[j].c-1);//統(tǒng)計貢獻到ans數(shù)組中 }for(j=l;j<i;j++)add(v[j].c,-v[j].w); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&v[i].q,&v[i].b,&v[i].c);v[i].w=1;if(v[i].q==2)swap(v[i].b,v[i].c),v[i].w=0,vis[i]=1;//標記每個操作是否需要輸出v[i].a=i;}cdq(1,m);//枚舉每個操作，需要輸出就輸出for(int i=1;i<=m;i++)if(vis[i])printf("%d\n",ans[i]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ivanovcraft/p/9692861.html

總結(jié)

以上是生活随笔為你收集整理的P2184 【贪婪大陆】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。