Magnificent Tree - 牛客網

​​https://www.nowcoder.com/acm/contest/106/H​​

分治就是講大問題劃分成許多小問題 也就是把1到num這些操作序列 劃分成許多小序列 對每個[l,r]的小序列 考慮l,m]這個小序列對[m+1,r]這個序列的影響 在這裡即是看左子序列的修改會對右子序列造成什麼影響

對每個子問題 右區間的查詢序要關心的是左區間當中在自己坐标範圍内的修改 以x或y兩者中的一個建立順序關系 然後用線段樹維護另一個 這樣就将一個二維線段樹的問題在空間複雜度上降了整整一維

當然動态主席樹也可以 但是空間吃不消 代碼略

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=5e5+10;
  
struct node
{
    int tp,x,y,val;
};
  
node order[maxm],tmp[maxm];
int sum[maxn],ans[maxn];
int n,q,tot,cnt;
  
int lowbit(int x)
{
    return x&(-x);
}
  
void update(int tar,int val)
{
    int i;
    for(i=tar;i<=n;i+=lowbit(i)) sum[i]+=val;
}
  
int query(int tar)
{
    int res,i;
    res=0;
    for(i=tar;i>=1;i-=lowbit(i)) res+=sum[i];
    return res;
}
  
void cdq(int l,int r)
{
    int m,i,p,q,pos;
    if(l==r) return;
    m=(l+r)/2;
    cdq(l,m),cdq(m+1,r);
    pos=l,p=l,q=m+1;
    while(p<=m&&q<=r){
        if(order[p].x<=order[q].x){
            if(order[p].tp==1) update(order[p].y,order[p].val);
            tmp[pos++]=order[p++];
        }
        else{
            if(order[q].tp==2) ans[order[q].val]-=query(order[q].y);
            else if(order[q].tp==3) ans[order[q].val]+=query(order[q].y);
            tmp[pos++]=order[q++];
        }
    }
    while(q<=r){
        if(order[q].tp==2) ans[order[q].val]-=query(order[q].y);
        else if(order[q].tp==3) ans[order[q].val]+=query(order[q].y);
        tmp[pos++]=order[q++];
    }
    for(i=l;i<=p-1;i++){
        if(order[i].tp==1) update(order[i].y,-order[i].val);
    }
    while(p<=m) tmp[pos++]=order[p++];
    for(i=l;i<=r;i++) order[i]=tmp[i];
}
  
int main()
{
    int i,tp,x1,y1,x2,y2,h;
    scanf("%d%d",&q,&n);
    for(i=1;i<=q;i++){
        scanf("%d",&tp);
        if(tp==1){
            scanf("%d%d%d",&x1,&y1,&h);
            order[++tot].tp=1,order[tot].x=x1,order[tot].y=y1,order[tot].val=h;
        }
        else{
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            cnt++;
            if(x1-1>=1) order[++tot].tp=2,order[tot].x=x1-1,order[tot].y=y2,order[tot].val=cnt;
            if(y1-1>=1) order[++tot].tp=2,order[tot].x=x2,order[tot].y=y1-1,order[tot].val=cnt;
            if(x1-1>=1&&y1-1>=1) order[++tot].tp=3,order[tot].x=x1-1,order[tot].y=y1-1,order[tot].val=cnt;
            order[++tot].tp=3,order[tot].x=x2,order[tot].y=y2,order[tot].val=cnt;
        }
    }
    cdq(1,tot);
    for(i=1;i<=cnt;i++) printf("%d\n",ans[i]);
    return 0;
}