Description

两个操作，往一个格子里加一个数和求给定矩形的权值和，强制在线，操作数\(\leq 200000\)

Solution 

直接上KD-tree

为了保证树的形态较为优美

每加入\(10000\)个数后，对KD-tree进行重构

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define reg registerinline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}const int MN=2e5+5;int N,F;struct Point{    int d[2],mn[2],mx[2],l,r,sum,val;    Point(){}    Point(int x,int y){d[0]=x,d[1]=y;}    Point(int x,int y,int x_,int y_){mn[0]=x,mn[1]=y;mx[0]=x_,mx[1]=y_;}    int&operator[](int x){return d[x];}    bool operator<(const Point&b)const{return d[F]
     
      =mn[0]&&b.mx[0]<=mx[0]&&b.mn[1]>=mn[1]&&b.mx[1]<=mx[1];}    inline bool out(const Point&b)const{return mn[0]>b.mx[0]||mx[0]
      
       b.mx[1]||mx[1]
       
        =mn[0]&&x<=mx[0]&&y>=mn[1]&&y<=mx[1];}}a[MN];struct KD_tree{    Point p[MN],T;    void up(int x)    {        int l=p[x].l,r=p[x].r;        for(int i=0;i<2;++i)        {            if(l) p[x].mn[i]=min(p[x].mn[i],p[l].mn[i]),                  p[x].mx[i]=max(p[x].mx[i],p[l].mx[i]);            if(r) p[x].mn[i]=min(p[x].mn[i],p[r].mn[i]),                  p[x].mx[i]=max(p[x].mx[i],p[r].mx[i]);            }        p[x].sum=p[l].sum+p[r].sum+p[x].val;    }    int build(int l,int r,int th)    {        if(l>r)return 0;int mid=l+r>>1;        F=th;std::nth_element(a+l,a+mid,a+r+1);        p[mid]=a[mid];        p[mid].mn[0]=p[mid].mx[0]=a[mid][0];        p[mid].mn[1]=p[mid].mx[1]=a[mid][1];        p[mid].l=build(l,mid-1,th^1);        p[mid].r=build(mid+1,r,th^1);        up(mid);        return mid;    }    int qry(int x)    {        if(!x)return 0;        if(T.in(p[x])) return p[x].sum;        if(T.out(p[x])) return 0;        int ret=0;        if(T.in(p[x].d[0],p[x].d[1])) ret+=p[x].val;        ret+=qry(p[x].l)+qry(p[x].r);        return ret;    }    void ins(int&x,int v,int th)    {        if(!x)        {            x=++N;p[x]=T;            for(reg int i=0;i<2;++i)                p[x].mn[i]=p[x].mx[i]=p[x][i];            p[x].sum=p[x].val=v;p[x].l=p[x].r=0;return;        }        if(p[x]==T){p[x].sum+=v;p[x].val+=v;return;}        if(T[th]
       
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！