二次联通门 :
/* luogu P3801 红色的幻想乡 两颗线段树 分别维护 X方向和Y方向 操作1就是异或1 操作2用容斥搞一搞就好 */#includevoid read (int &now){ now = 0; register char word = getchar (); while (word < '0' || word > '9') word = getchar (); while (word >= '0' && word <= '9') { now = now * 10 + word - '0'; word = getchar (); }}struct S_D { S_D *Left, *Right; int key; int Mid; int l, r; S_D (int __l, int __r) : l (__l), r (__r), key (0) { Mid = (__l + __r) >> 1; Left = Right = NULL; }; S_D () {}; inline void Updata () { this->key = this->Left->key + this->Right->key; }};class Segment_Tree_Type{ private : S_D *Root; void __Build_ (S_D *&now, int l, int r) { now = new S_D (l, r); if (l == r) return ; __Build_ (now->Left, l, now->Mid); __Build_ (now->Right, now->Mid + 1, r); now->Updata (); } int Query (S_D *&now, int l, int r) { if (l <= now->l && now->r <= r) return now->key; register int res = 0; if (l <= now->Mid) res += Query (now->Left, l, r); if (r > now->Mid) res += Query (now->Right, l, r); return res; } void __Change_ (S_D *&now, int pos) { if (now->l == now->r) { now->key ^= 1; return ; } if (pos <= now->Mid) __Change_ (now->Left, pos); else __Change_ (now->Right, pos); now->Updata (); } public : inline void Build (int l, int r) { __Build_ (Root, l, r); return ; } inline void Change (int pos) { __Change_ (Root, pos); return ; } inline int Query (int l, int r) { return Query (Root, l, r); }};Segment_Tree_Type X, Y;int main (int argc, char *argv[]){ int M, N, x, y; read (N); read (M); X.Build (1, N); Y.Build (1, M); int type, Q; int _x, _y; long long now_1, now_2; for (read (Q); Q --; ) { read (type); read (x); read (y); if (type == 1) { X.Change (x); Y.Change (y); } else { read (_x); read (_y); now_1 = X.Query (x, _x); now_2 = Y.Query (y, _y); printf ("%lld\n", now_1 * (long long) (_y - y + 1) + now_2 * (long long) (_x - x + 1) - now_1 * now_2 * 2LL); } } return 0;}