这题强制在线，只能用k-d tree了，否则可以用cdq分治。 刚开始我想仿照二维线段树的做法，只不过每一层把一个矩形沿一维切一刀。这样的话复杂度是\(O(mlog ^ 2 n)\)的，还是能过。刚想写发现内存只有20M，这不gg了。 最后还是看了题解。 题解果然跟我不一样，最大的区别是查询的时候忽略了没有修改过的点，大大的提高了速度。 把修改看成添加点，然后因为k-d tree的结构是平衡树结构，所以添加的时候就按跟平衡树一样添加：每次比较添加点和这个节点上的点在这一维上的大小，好决定往左右子树插入。 因为没有旋转，所以肯定会不平衡。所以我们需要定时重构，有两种方法： 1.模仿替罪羊树重构。当子树大小大于该节点所在子树*平衡因子时，把整个子树重构。 2.每插入5000个节点，把整棵树重构。 我用的是第二种方法。 查询和线段树有些不一样，就是查询区间在递归的时候是不变的。所以每次只判断当前矩形时是否全在查询矩形范围内，或者全不在，以及该节点是否在矩形内。否则我们就往子树递归。 我的代码跑的好像挺慢的，比第一种重构方法慢了不少。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define In inlinetypedef long long ll;typedef double db;const int INF = 0x3f3f3f3f;const db eps = 1e-8;const int maxm = 2e5 + 5;const int SIZE = 5000;inline ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}inline void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}int n, Dim;struct Node{ int ch[2]; int d[2], Min[2], Max[2]; int val, sum; In bool operator < (const Node& oth)const { return d[Dim] < oth.d[Dim]; } In bool operator == (const Node& oth)const { return d[0] == oth.d[0] && d[1] == oth.d[1]; }}t[maxm], a[maxm];int root, tcnt = 0, cnt = 0;In void new_node(int& now, Node a){ t[now = ++tcnt] = a; t[now].sum = t[now].val; for(int i = 0; i < 2; ++i) { t[now].ch[i] = 0; t[now].Min[i] = t[now].Max[i] = t[now].d[i]; }}In void pushup(const int& now){ t[now].sum = t[t[now].ch[0]].sum + t[t[now].ch[1]].sum + t[now].val; for(int i = 0; i < 2; ++i) { if(t[now].ch[0]) { t[now].Min[i] = min(t[now].Min[i], t[t[now].ch[0]].Min[i]); t[now].Max[i] = max(t[now].Max[i], t[t[now].ch[0]].Max[i]); } if(t[now].ch[1]) { t[now].Min[i] = min(t[now].Min[i], t[t[now].ch[1]].Min[i]); t[now].Max[i] = max(t[now].Max[i], t[t[now].ch[1]].Max[i]); } }}In void build(int& now, const int& L, const int& R, const int& d){ if(L > R) return; int mid = (L + R) >> 1; Dim = d; nth_element(a + L, a + mid, a + R + 1); new_node(now, a[mid]); build(t[now].ch[0], L, mid - 1, d ^ 1); build(t[now].ch[1], mid + 1, R, d ^ 1); pushup(now);}In void insert(int& now, Node a, const int& d){ if(!now) {new_node(now, a); return;} if(a.d[d] <= t[now].d[d]) insert(t[now].ch[0], a, d ^ 1); else insert(t[now].ch[1], a, d ^ 1); pushup(now);}int d1[2], d2[2];In bool in(const int& now){ for(int i = 0; i < 2; ++i) if(t[now].Min[i] >= d1[i] && t[now].Max[i] <= d2[i]) continue; else return 0; return 1;}In bool out(const int& now) //刚开始这个写错了，狂TLE不止{ for(int i = 0; i < 2; ++i) if(t[now].Min[i] > d2[i] || t[now].Max[i] < d1[i]) return 1; return 0;}In bool in_point(const int& now){ for(int i = 0; i < 2; ++i) if(t[now].d[i] < d1[i] || t[now].d[i] > d2[i]) return 0; return 1;}In ll query(const int& now){ if(!now) return 0; if(in(now)) return t[now].sum; if(out(now)) return 0; //全不在查询矩形内 int ret = 0; if(in_point(now)) ret += t[now].val; ret += query(t[now].ch[0]) + query(t[now].ch[1]); return ret;}int main(){// freopen("random.in", "r", stdin);// freopen("ac.out", "w", stdout); n = read(); int ans = 0; while(1) { int op = read(); if(op == 3) break; else if(op == 1) { a[++cnt].d[0] = read() ^ ans; a[cnt].d[1] = read() ^ ans, a[cnt].val = read() ^ ans; if(cnt % SIZE == 0) { tcnt = 0; build(root, 1, cnt, 0); } else insert(root, a[cnt], 0); } else { d1[0] = read() ^ ans, d1[1] = read() ^ ans, d2[0] = read() ^ ans, d2[1] = read() ^ ans; ans = query(root); write(ans), enter; } } return 0;}