省选模拟 19/11/05

省选模拟 19/11/05

黑白划分
最后答案的个数就是非纯色正方形的个数
考虑容斥，用总的减去纯色的
发现对每一个纯色的都要减去它覆盖的四个的贡献，而这样减正好能减完，令 f ( i ) f(i) f(i) 表示边长为 2 i 2^i 2i 的个数
a n s = ∑ i = 0 n ( 2 n − i ) 2 − 4 ∗ f ( i ) ∗ [ i > 0 ] ans=sum_{i=0}^n(2^{n-i})^2-4*f(i)*[i>0] ans=i=0∑n​(2n−i)2−4∗f(i)∗[i>0]
然后发现两个维度是独立的，我们对两个维度分别求出它的连续纯色区间个数，乘起来就是答案
分离两个维度的考虑巧妙

#include<bits/stdc++.h>
#define cs const
using namespace std;
int read(){int cnt = 0, f = 1; char ch = 0;while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();return cnt * f;
}
cs int N = 21, M = 1 << 20 | 5;
typedef long long ll;
int n, q, S, lg[M];
struct Segmentree{int sum[M << 2], ct[N];#define mid ((l+r)>>1)void pushup(int x, int l, int r){int pre = sum[x];sum[x] = sum[x<<1] + sum[x<<1|1];if((pre == 0 && sum[x] == 1) || (pre == r-l+1 && sum[x] == r-l)) --ct[lg[r-l+1]];else if((pre == 1 && sum[x] == 0) || (pre == r-l && sum[x] == r-l+1)) ++ct[lg[r-l+1]];}void build(int x, int l, int r){ct[lg[r - l + 1]]++;if(l == r) return; build(x<<1, l, mid); build(x<<1|1, mid+1, r);}void modify(int x, int l, int r, int p){if(l == r){ sum[x] ^= 1; return; }if(p <= mid) modify(x<<1, l, mid, p);else modify(x<<1|1, mid+1, r, p);pushup(x, l, r);}
}seg[2];
int main(){n = read(), q = read(); S = 1 << n;for(int i = 2; i <= S; i++) lg[i] = lg[i>>1] + 1; seg[0].build(1, 1, S);seg[1].build(1, 1, S);while(q--){int op = read(), x = read();seg[op].modify(1, 1, S, x);ll ans = 0;for(int i = 0; i <= n; i++){ll ret = 1ll * seg[0].ct[i] * seg[1].ct[i];ans += 1ll << ((n - i) << 1);if(i) ans -= ret << 2;} cout << ans << 'n';} return 0;
}

1959 年式中型坦克
首先暴力的做法是两边分别按 y y y 排序，每次枚举两个点，删除两边的后缀判断联不联通
发现双指针维护即可，先把第一个序列插入，然后每次删除一个点以及相连的边
下面的序列插入，直到联通
发现可以用 l c t lct lct 维护，但有一个问题是可能形成环，这时候我们需要删掉环上 y u y_u yu​ 最大的也就是应该被最先退掉的点，需要维护一个链上最大，拆边为点即可
然后还需要支持判断有没有联通，也就是一个连通块的关键点的个数或者权值之和
l c t lct lct 维护虚子树信息即可

#include<bits/stdc++.h>
#define cs const
#define y1 y_1
#define y2 y_2
#define re register
using namespace std;
int read(){int cnt = 0, f = 1; char ch = 0;while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();return cnt * f;
}
cs int N = 7e5 + 5;
typedef long long ll;
ll gcd(ll a, ll b){ return !b ? a : gcd(b, a % b); }
int n, m1, m2;
int y1[N], y2[N], b[N];
vector<int> e1[N], e2[N];
vector<int> nd1[N], nd2[N];
int tot, ec, ct1, ct2;
struct edge{ int u, v; } e[N];
int pos[N], p1[N], p2[N];
int val[N], tim[N];
#define pb push_back
namespace LCT{int ch[N][2], fa[N], sum[N], sub[N], mx[N]; // sub 维护虚子树  bool rev[N];#define ls ch[x][0]#define rs ch[x][1]bool isr(int x){return ch[fa[x]][0] != x && ch[fa[x]][1] != x;}void pushrev(int x){ if(!x) return; rev[x] ^= 1; swap(ls, rs); }void pushdown(int x){ if(rev[x]) pushrev(ls), pushrev(rs), rev[x] = 0; }void pushup(int x){sum[x] = sum[ls] + sum[rs] + val[x] + sub[x]; mx[x] = x;if(tim[mx[ls]] > tim[mx[x]]) mx[x] = mx[ls];if(tim[mx[rs]] > tim[mx[x]]) mx[x] = mx[rs];}void pushpath(int x){ if(!isr(x)) pushpath(fa[x]); pushdown(x); } void rotate(int x){int y = fa[x], z = fa[y], k = ch[y][1] == x;if(!isr(y)) ch[z][ch[z][1] == y] = x; fa[x] = z; ch[y][k] = ch[x][k^1]; fa[ch[x][k^1]] = y;ch[x][k^1] = y; fa[y] = x; pushup(y); pushup(x);}void splay(int x){pushpath(x);while(!isr(x)){int y = fa[x], z = fa[y];if(!isr(y)) rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y);rotate(x);} pushup(x);} void access(int x){for(int y = 0; x; y = x, x = fa[x]){splay(x); if(rs) sub[x] += sum[rs];if(y) sub[x] -= sum[y]; rs = y;pushup(x);}}int findrt(int x){access(x); splay(x); pushdown(x); while(ls) x = ls, pushdown(x); return x; }void mkroot(int x){ access(x); splay(x); pushrev(x); } bool in(int x, int y){mkroot(x); return findrt(y) == x; }void link(int x, int y){ mkroot(x); access(y); splay(y); fa[x] = y; sub[y] += sum[x]; pushup(y); }void cut(int x, int y){ mkroot(x); access(y); splay(y); fa[x] = ch[y][0] = 0; pushup(x); pushup(y); }int qsz(int x){ access(x); splay(x);  return sum[x]; }int find(int x, int y){ mkroot(x); access(y); splay(y); return mx[y]; } 
}	
int main(){n = read(), m1 = read(), m2 = read();tot = n + m1 + n + m2;for(int i = 1; i <= m1; i++) p1[i] = ++tot;for(int i = 1; i <= m2; i++) p2[i] = ++tot;for(int i = 1; i <= n; i++) pos[i] = ++tot, val[tot] = 1;for(int i = 1; i <= m1; i++) y1[i] = read(), b[i] = y1[i] = read();sort(b + 1, b + m1 + 1); ct1 = unique(b + 1, b + m1 + 1) - (b + 1);for(int i = 1; i <= m1; i++){y1[i] = lower_bound(b + 1, b + ct1 + 1, y1[i]) - b;nd1[y1[i]].pb(i);}for(int i = 1; i < n + m1; i++){int t = read(), u = read(), v = read();if(t == 1){e[++ec] = (edge){ pos[u], p1[v] };e1[v].pb(ec); tim[ec] = y1[v];LCT::link(ec, pos[u]);LCT::link(ec, p1[v]);} else{e[++ec] = (edge){ p1[u], p1[v] };if(y1[u] > y1[v]) e1[u].pb(ec), tim[ec] = y1[u];else e1[v].pb(ec), tim[ec] = y1[v];LCT::link(ec, p1[u]);LCT::link(ec, p1[v]);}}for(int i = 1; i <= m2; i++) y2[i] = read(), b[i] = y2[i] = abs(read());sort(b + 1, b + m2 + 1); ct2 = unique(b + 1, b + m2 + 1) - (b + 1);for(int i = 1; i <= m2; i++){y2[i] = lower_bound(b + 1, b + ct2 + 1, y2[i]) - b;nd2[y2[i]].pb(i);}for(int i = 1; i < n + m2; i++){int t = read(), u = read(), v = read();if(t == 1){e[++ec] = (edge){ pos[u], p2[v] };e2[v].pb(ec);  } else{e[++ec] = (edge){ p2[u], p2[v] };if(y2[u] > y2[v]) e2[u].pb(ec);else e2[v].pb(ec);}} ll ans = 0, all = (ll)m1 * m2;for(int i = ct1, j = 1, now = 0; i >= 1; i--){for(int o = 0; o < nd1[i].size(); o++){int u = nd1[i][o];for(int k = 0; k < e1[u].size(); k++){int nx = e1[u][k];if(LCT::in(e[nx].u, nx)) LCT::cut(e[nx].u, nx);if(LCT::in(e[nx].v, nx)) LCT::cut(e[nx].v, nx);}}while(j <= ct2 && LCT::qsz(pos[1]) < n){for(int o = 0; o < nd2[j].size(); o++){int u = nd2[j][o];for(int k = 0; k < e2[u].size(); k++){int nx = e2[u][k];if(LCT::in(e[nx].u, e[nx].v)){int p = LCT::find(e[nx].u, e[nx].v);	LCT::cut(p, e[p].u); LCT::cut(p, e[p].v);}LCT::link(nx, e[nx].u);LCT::link(nx, e[nx].v);} } now += nd2[j++].size();} ans += 1ll * nd1[i].size() * (m2 - now);} if(ans == 0) puts("0");else if(ans == all) puts("1");else{ll g = gcd(ans, all);cout << ans / g << "/" << all / g;} return 0;
}