关键词：线段树
二维线段树维护一个 维护一个X线段的线段树，每个X节点维护一个 维护一个Y线段的线段树。
注意，以下代码没有PushDownX。因为如果要这么做，PushDownX时，由于当前X节点的子节点可能存在标记，而标记不能叠加，导致每次PushDownX时都要把子节点PushDownX一次。每次PushDownX都要对子节点UpdateY，代价太高。这种情况下原则是：只有查询操作<<更新操作时才PushDownX。
#include#include #include #include using namespace std;const int MAX_X = 2000, MAX_Y = 2000;struct RangeTree2d{ private: bool Rev[MAX_X * 4][MAX_Y * 4]; int YlMin, YrMax, XlMin, XrMax; void PushDownY(int xCur, int yCur) { if (Rev[xCur][yCur]) { Rev[xCur][yCur * 2] ^= 1; Rev[xCur][yCur * 2 + 1] ^= 1; Rev[xCur][yCur] = false; } } void UpdateY(int xCur, int yCur, int sl, int sr, int al, int ar) { assert(sl <= sr&&al <= ar&&al <= sr&&ar >= sl); if (al <= sl&&sr <= ar) { Rev[xCur][yCur] ^= 1; return; } int mid = (sr - sl) / 2 + sl; if (al <= mid) UpdateY(xCur, yCur * 2, sl, mid, al, ar); if (ar > mid) UpdateY(xCur, yCur * 2 + 1, mid + 1, sr, al, ar); } void UpdateY(int xCur, int l, int r) { UpdateY(xCur, 1, YlMin, YrMax, l, r); } bool QueryY(int xCur, int yCur, int l, int r, int y) { if (l == r) return Rev[xCur][yCur]; PushDownY(xCur, yCur); int mid = (l + r) / 2; if (y <= mid) return QueryY(xCur, yCur * 2, l, mid, y); else return QueryY(xCur, yCur * 2 + 1, mid + 1, r, y); } bool QueryY(int xCur, int y) { return QueryY(xCur, 1, YlMin, YrMax, y); } void UpdateX(int xCur, int sl, int sr, int al, int ar, int yl, int yr) { //printf("C x:sl %d sr %d al %d ar %d\n", sl, sr, al, ar); assert(sl <= sr&&al <= ar&&al <= sr&&ar >= sl); if (al <= sl&&sr <= ar) { UpdateY(xCur, yl, yr); return; } int mid = (sr - sl) / 2 + sl; if (al <= mid) UpdateX(xCur * 2, sl, mid, al, ar, yl, yr); if (ar > mid) UpdateX(xCur * 2 + 1, mid + 1, sr, al, ar, yl, yr); } void QueryX(int xCur, int l, int r, int x, int y, bool &ans) { ans ^= QueryY(xCur, y); if (l == r) return; int mid = (l + r) / 2; if (x <= mid) QueryX(xCur * 2, l, mid, x, y, ans); else QueryX(xCur * 2 + 1, mid + 1, r, x, y, ans); }public: void Init(int xlMin, int xrMax, int ylMin, int yrMax) { XlMin = xlMin; XrMax = xrMax; YlMin = ylMin; YrMax = yrMax; memset(Rev, false, sizeof(Rev)); } void Update(int xl, int xr, int yl, int yr) { UpdateX(1, XlMin, XrMax, xl, xr, yl, yr); } int Query(int x, int y) { bool ans = false; QueryX(1, XlMin, XrMax, x, y, ans); return ans; }}g;int main(){#ifdef _DEBUG freopen("c:\\noi\\source\\input.txt", "r", stdin);#endif int totCase; scanf("%d", &totCase); while (totCase--) { int mSize, qCnt; scanf("%d%d", &mSize, &qCnt); g.Init(1, mSize, 1, mSize); while (qCnt--) { char op; int x1, x2, y1, y2; scanf("\n%c", &op); switch (op) { case 'C': scanf("%d%d%d%d", &x1, &y1, &x2, &y2); g.Update(x1, x2, y1, y2); break; case 'Q': scanf("%d%d", &x1, &y1); printf("%d\n", g.Query(x1, y1)); break; default: assert(0); } } printf("\n"); } return 0;}
反思：
1.不用动态开点，因为内存够。动态申请内存费时间。
2.不要将问题扩大化为求区域面积，提高了编程复杂度。