题目概述

单点加，矩阵求和，强制在线。

解题报告

强制在线还卡空间，所以我们用KDT吧QAQ！每个节点记录一下控制区域和控制区域内的和，每次查询的时候不停找和询问区域有交集的节点就行了。好像KDT处理矩阵问题复杂度是正常的，是 $O(n\sqrt n)$ ？

为了防止插入效率爆炸所以我们可以用替罪羊树的方案进行重构。

不知道为什么这样跑得比暴力重构（隔 $10000$ 次重构一次）慢多了……而且我自带大常数，两种方法都加上去才卡过……

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=200000;
 
int n,D,ro,son[maxn+5][2],MN[maxn+5][2],MX[maxn+5][2],si[maxn+5],sum[maxn+5],Tail,que[maxn+5],*sg,ans;
struct Point {int x[2],v;inline bool operator < (const Point &a) const {return x[D]<a.x[D];}} a[maxn+5];
 
#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline void Pushup(int p){
    for (int i=0;i<2;i++) MN[p][i]=MX[p][i]=a[p].x[i];
    si[p]=si[son[p][0]]+1+si[son[p][1]];sum[p]=sum[son[p][0]]+a[p].v+sum[son[p][1]];
    for (int j=0;j<2;j++)
        for (int i=0;son[p][j]&&i<2;i++)
            MN[p][i]=min(MN[p][i],MN[son[p][j]][i]),MX[p][i]=max(MX[p][i],MX[son[p][j]][i]);
}
inline bool cmp(const int &p,const int &q) {return a[p]<a[q];}
int Build(int L,int R,int d=0){
    int m=L+(R-L>>1);D=d;nth_element(que+L,que+m,que+R+1,cmp);int p=que[m];son[p][0]=son[p][1]=0;
    if (L<m) son[p][0]=Build(L,m-1,d^1);if (m<R) son[p][1]=Build(m+1,R,d^1);Pushup(p);return p;
}
void ins(int &p,int d=0){
    if (!p) return Pushup(p=n);D=d;ins(son[p][a[p]<a[n]],d^1);Pushup(p);
    if (max(si[son[p][0]],si[son[p][1]])>si[p]*0.75) sg=&p;
}
void Dfs(int p) {if (!p) return;Dfs(son[p][0]);que[++Tail]=p;Dfs(son[p][1]);}
inline void Insert(int &p) {sg=0;ins(ro);if (sg) Tail=0,Dfs(*sg),*sg=Build(1,Tail);}
int Ask(int p,int A,int B,int C,int D){
    if (!p||B<MN[p][0]||MX[p][0]<A||D<MN[p][1]||MX[p][1]<C) return 0;
    if (A<=MN[p][0]&&MX[p][0]<=B&&C<=MN[p][1]&&MX[p][1]<=D) return sum[p];
    int val=(A<=a[p].x[0]&&a[p].x[0]<=B&&C<=a[p].x[1]&&a[p].x[1]<=D?a[p].v:0);
    return Ask(son[p][0],A,B,C,D)+val+Ask(son[p][1],A,B,C,D);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int ti=(readi(n),n=0,10000);;){
        int tp,A,B,C,D;readi(tp);if (tp==3) break;
        readi(A);readi(B);readi(C);A^=ans;B^=ans;C^=ans;
        if (tp==1){
            n++;a[n].x[0]=A;a[n].x[1]=B;a[n].v=C;Insert(ro);
            if (--ti==0) ti=10000,Tail=0,Dfs(ro),ro=Build(1,Tail);
        } else readi(D),D^=ans,printf("%d\n",ans=Ask(ro,A,C,B,D));
    }return 0;
}