题意：对于点集S，定义函数F(S)为对S不断扩展到不能扩展时S的点数。一次扩展定义为如果有一个平行于坐标轴的矩形的三个点在S中，则第四个点加入S。

动态在S中加点删点，每次操作完后求F(S)的值。

解：首先有个结论就是，把这些点用平行于坐标轴的线段连接起来，则E值为每个连通块的横坐标种数 * 纵坐标种数之和。

线段树分治 + 可回退化并查集，O(nlog²n)。

1 #include 
      
         2   3 typedef long long LL;  4 const int N = 300010;  5   6 struct Node {  7     int x, y;  8     Node(int X, int Y) {  9         x = X; 10         y = Y; 11     } 12 }; 13  14 std::map
       
         mp[N]; 15 int n, m; 16 LL ans[N]; 17 std::vector
        
          v[N << 2]; 18  19 namespace ufs { 20      21     struct opt { 22         int x, y; 23         opt(){} 24         opt(int X, int Y) { 25             x = X, y = Y; 26         } 27     }stk[N * 4]; int top; 28      29     int fa[N * 2], siz[N * 2], s1[N * 2], s2[N * 2], clock; 30     LL tot, stk2[N]; 31     inline void init() { 32         for(int i = 1; i < N; i++) { 33             fa[i] = i; 34             fa[i + N] = i + N; 35             siz[i] = siz[i + N] = 1; 36             s1[i] = s2[i + N] = 1; 37             s2[i] = s1[i + N] = 0; 38         } 39         top = clock = 0; 40         return; 41     } 42     int find(int x) { 43         if(x == fa[x]) return x; 44         return find(fa[x]); 45     } 46     inline LL cal(int x) { 47         return 1ll * s1[x] * s2[x]; 48     } 49     inline void merge(int x, int y) { 50         x = find(x); 51         y = find(y); 52         if(x == y) return; 53         if(siz[x] < siz[y]) { 54             std::swap(x, y); 55         } 56         stk2[++clock] = tot; 57         tot -= cal(x) + cal(y); 58         stk[++top] = opt(y, fa[y]); 59         fa[y] = x; 60         stk[++top] = opt(x, siz[x]); 61         siz[x] += siz[y]; 62         stk[++top] = opt(x, s1[x]); 63         s1[x] += s1[y]; 64         stk[++top] = opt(x, s2[x]); 65         s2[x] += s2[y]; 66         tot += cal(x); 67         return; 68     } 69     inline void erase(int t) { 70         while(clock > t) { 71             tot = stk2[clock--]; 72             s2[stk[top].x] = stk[top].y; 73             top--; 74             s1[stk[top].x] = stk[top].y; 75             top--; 76             siz[stk[top].x] = stk[top].y; 77             top--; 78             fa[stk[top].x] = stk[top].y; 79             top--; 80         } 81         return; 82     } 83 } 84  85 void add(int L, int R, Node x, int l, int r, int o) { 86     if(L <= l && r <= R) { 87         v[o].push_back(x); 88         return; 89     } 90     int mid = (l + r) >> 1; 91     if(L <= mid) { 92         add(L, R, x, l, mid, o << 1); 93     } 94     if(mid < R) { 95         add(L, R, x, mid + 1, r, o << 1 | 1); 96     } 97     return; 98 } 99 100 void solve(int l, int r, int o) {101     int now = ufs::clock;102     for(int i = 0; i < (int)v[o].size(); i++) {103         ufs::merge(v[o][i].x, v[o][i].y + N);104         //printf("[%d %d] merge %d %d \n", l, r, v[o][i].x, v[o][i].y);105     }106     if(l == r) {107         ans[r] = ufs::tot;108         ufs::erase(now);109         return;110     }111     int mid = (l + r) >> 1;112     solve(l, mid, o << 1);113     solve(mid + 1, r, o << 1 | 1);114     ufs::erase(now);115     return;116 }117 118 int main() {119     ufs::init();120     scanf("%d", &n);121     for(int i = 1, x, y; i <= n; i++) {122         scanf("%d%d", &x, &y);123         if(mp[x][y]) {124             add(mp[x][y], i - 1, Node(x, y), 1, n, 1);125             //printf("add : (%d %d) [%d %d] \n", x, y, mp[x][y], i - 1);126             mp[x][y] = 0;127         }128         else {129             mp[x][y] = i;130         }131     }132     std::map
         
          ::iterator it;133     for(int i = 1; i < N; i++) {134         for(it = mp[i].begin(); it != mp[i].end(); it++) {135             if(it->second) {136                 add(it->second, n, Node(i, it->first), 1, n, 1);137                 //printf("add : (%d %d) [%d %d] \n", i, it->first, it->second, n);138             }139         }140     }141     142     solve(1, n, 1);143     for(int i = 1; i <= n; i++) {144         printf("%lld ", ans[i]);145     }146     return 0;147 }