T1
主观难度：【0】
懒的写。
T2
主观难度：【0】
其实树上倍增和树剖都能做。
这里我懒得思考了于是花了 20 min 打了一个树剖。
T3
主观难度：【1】
简单组合数学题。草因为没看见最短路径数不超过 \(2^{15}\) 卡题了。
对于每个公民算出每个点到 \(s\) 和 \(t\) 的路径数，乘起来就得到了经过一个点的总路径数，然后加起来算一下即可。
#include <bits/stdc++.h>
#define llong long long
#define N 5003
#define M 40004
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n, m, k, ans;
int to[M<<1], nxt[M<<1], head[N], gsiz;
#define mkarc(u,v) (++gsiz, to[gsiz]=v, nxt[gsiz]=head[u], head[u]=gsiz)
int dis1[N], dis2[N], cnt1[N], cnt2[N];
double e[N];int que[N], he, ta;
inline void prework1(int s, int *dis){for(int i = 1; i <= n; ++i) dis[i] = 1e9+7;que[he = ta = 1] = s, dis[s] = 0;while(he <= ta){int u = que[he++];for(int i = head[u]; i; i = nxt[i]){int v = to[i];if(dis[v] > dis[u]+1){dis[v] = dis[u]+1;que[++ta] = v;}}}return;
}
int vis[N];
inline void prework2(int s, int t, int *d1, int *d2, int *cnt){for(int i = 1; i <= n; ++i) cnt[i] = vis[i] = 0;que[he = ta = 1] = s, cnt[s] = 1;while(he <= ta){int u = que[he++];for(int i = head[u]; i; i = nxt[i]){int v = to[i];if(d1[u]+1+d2[v] != d1[t]) continue;cnt[v] += cnt[u];if(!vis[v]) vis[que[++ta] = v] = true;}}return;
}
inline void calc(int s, int t){prework1(s, dis1), prework1(t, dis2);prework2(s, t, dis1, dis2, cnt1);prework2(t, s, dis2, dis1, cnt2);for(int i = 1; i <= n; ++i)e[i] += 1.0*cnt1[i]*cnt2[i]/cnt1[t];return;
}int main(){freopen("in.txt", "r", stdin);read(n, m);for(int i = 1; i <= m; ++i){int u, v;read(u, v), ++u, ++v;mkarc(u, v), mkarc(v, u);}read(k);for(int i = 1; i <= k; ++i){int s, t;read(s, t), ++s, ++t;calc(s, t);}for(int i = 1; i <= n; ++i)if(e[ans] < e[i]) ans = i;printf("%d", ans-1);return 0;
}T4
主观难度：【0】
懒的写。
#include <bits/stdc++.h>
#define llong long long
#define N 100005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n, q;
int b[N];struct Node{int l, r, k;
} a[N];
int l[N], r[N];int val[N<<2], tag[N<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)inline void pushup(int x){val[x] = min(val[ls(x)], val[rs(x)]);return;
}
inline void addtag(int x, int k){val[x] = max(val[x], k), tag[x] = max(tag[x], k);return;
}
inline void pushdown(int x){if(tag[x] == 0) return;addtag(ls(x), tag[x]), addtag(rs(x), tag[x]);tag[x] = 0;return;
}
inline void modify(int L, int R, int k, int x = 1, int l = 1, int r = n){if(L > R) return;if(L <= l && R >= r) return addtag(x, k);pushdown(x);if(L <= mid) modify(L, R, k, ls(x), l, mid );if(R > mid) modify(L, R, k, rs(x), mid+1, r);pushup(x);return;
}
inline int getlower(int L, int R, int k, int x = 1, int l = 1, int r = n){if(val[x] > k) return -1;if(l == r) return l;pushdown(x);if(R <= mid) return getlower(L, R, k, ls(x), l, mid );if(L > mid) return getlower(L, R, k, rs(x), mid+1, r);int res = getlower(L, R, k, ls(x), l, mid);if(res > -1) return res;else return getlower(L, R, k, rs(x), mid+1, r);
}int main(){
// freopen("in.txt", "r", stdin);read(n, q);for(int i = 1; i <= q; ++i){read(a[i].l, a[i].r, a[i].k);++a[i].l, ++a[i].r, ++a[i].k;modify(a[i].l, a[i].r, a[i].k);}sort(a+1, a+q+1, [&](Node o1, Node o2){return o1.k<o2.k;});for(int i = 1; i <= n; ++i) l[i] = 1, r[i] = n;for(int i = 1; i <= q; ++i){l[a[i].k] = max(l[a[i].k], a[i].l);r[a[i].k] = min(r[a[i].k], a[i].r);}for(int i = 1; i <= n; ++i){if(l[i] > r[i]){for(int j = 1; j <= n; ++j) printf("-1 ");return 0;}int pos = getlower(l[i], r[i], i);if(pos == -1){for(int j = 1; j <= n; ++j) printf("-1 ");return 0;}modify(pos, pos, 1e9+7);b[pos] = i-1;}for(int i = 1; i <= n; ++i) printf("%d ", b[i]);return 0;
}T5
主观难度：【2】
何意味。
首先建重构树，然后题目就变成了单点加区间数颜色。听说可以用带修莫队搞出来 \(\mathrm O(nq^{\frac{2}{3}})\) 但是我懒。而且这么做好像不是很优的样子。
于是我们使用一种方法把这个东西变成离线动态二维数点。具体地，我们对每个位置建 \((x_i, x_i, 1)\)，且对两个颜色相同距离极小的位置建 \((x_j, x_i, -1)\)。这样的意义是取颜色相同的点里位置最大的来计数。
然后随便整一个离线动态二维数点即可，树套树或者 cdq 反正都是 \(\mathrm O(n \log^2 n)\)，没什么区别。
#include <bits/stdc++.h>
#define llong long long
#define N 100005
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n, m, q;
#define pos(x,y) ((x-1)*m+y)
int a[N], b[N], fa[N][21];struct Node{int x, y, val;
} tmp[N];int f[N];
inline int find(int x){if(x == f[x]) return x;return f[x] = find(f[x]);
}vector<int> G[N];
int lpos[N], rpos[N], dfcnt;
inline void dfs(int u){lpos[u] = ++dfcnt;for(int i = 1; i <= 20; ++i) fa[u][i] = fa[fa[u][i-1]][i-1];for(int v : G[u]) dfs(v);rpos[u] = dfcnt;
}int root[N];
int val[N<<8], ls[N<<8], rs[N<<8], tsiz;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)inline int newnode(){return ++tsiz;
}
inline void pushup(int x){val[x] = val[ls[x]]+val[rs[x]];return;
}
inline void addtag(int x, int k){val[x] += k;return;
}
inline void modify(int pos, int k, int& x, int l = 1, int r = n*m){if(!x) x = newnode();if(l == r) return addtag(x, k);if(pos <= mid) modify(pos, k, ls[x], l, mid );else modify(pos, k, rs[x], mid+1, r);pushup(x);return;
}
inline int query(int L, int R, int &x, int l = 1, int r = n*m){if(!x) return 0;if(L <= l && R >= r) return val[x];int res = 0;if(L <= mid) res += query(L, R, ls[x], l, mid );if(R > mid) res += query(L, R, rs[x], mid+1, r);return res;
}#define lowbit(x) (x&-x)inline void modifynode(int x, int y, int k){for(int i = x; i <= n*m; i += lowbit(i)) modify(y, k, root[i]);return;
}
inline int querymatrix(int x1, int y1, int x2, int y2){int res = 0;for(int i = x2; i; i ^= lowbit(i)) res += query(y1, y2, root[i]);for(int i = x1-1; i; i ^= lowbit(i)) res -= query(y1, y2, root[i]);return res;
}set<int> col[N];inline void modifycol(int pos, int k){int dfn = lpos[pos];// Remove from colorset<int>::iterator it1, it2;it1 = it2 = col[b[pos]].lower_bound(dfn);int pos1 = 0, pos2 = 0;if(it1 != col[b[pos]].begin()) pos1 = *--it1;if(++it2 != col[b[pos]].end()) pos2 = *it2;if(pos1) modifynode(dfn, pos1, 1);if(pos2) modifynode(pos2, dfn, 1);if(pos1 && pos2) modifynode(pos2, pos1, -1);col[b[pos]].erase(dfn);b[pos] = k;// Add to colorit1 = it2 = col[b[pos]].lower_bound(dfn);pos1 = pos2 = 0;if(it1 != col[b[pos]].begin()) pos1 = *--it1;if(it2 != col[b[pos]].end()) pos2 = *it2;if(pos1) modifynode(dfn, pos1, -1);if(pos2) modifynode(pos2, dfn, -1);if(pos1 && pos2) modifynode(pos2, pos1, 1);col[b[pos]].insert(dfn);return;
}
inline int queryint(int l, int r){return querymatrix(l, l, r, r);
}int main(){
// freopen("in.txt", "r", stdin);read(n, m, q);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j) read(a[pos(i, j)]);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j) read(b[pos(i, j)]);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)tmp[pos(i, j)] = (Node){i, j, a[pos(i, j)]};sort(tmp+1, tmp+n*m+1, [&](Node o1, Node o2){return o1.val<o2.val;});for(int i = 1; i <= n*m*2; ++i) f[i] = i;for(int i = 1; i <= n*m; ++i){int x = tmp[i].x, y = tmp[i].y;if(x != 1 && a[find(pos(x-1,y))] < tmp[i].val) f[find(pos(x-1,y))] = fa[find(pos(x-1,y))][0] = pos(x, y);if(y != 1 && a[find(pos(x,y-1))] < tmp[i].val) f[find(pos(x,y-1))] = fa[find(pos(x,y-1))][0] = pos(x, y);if(x != n && a[find(pos(x+1,y))] < tmp[i].val) f[find(pos(x+1,y))] = fa[find(pos(x+1,y))][0] = pos(x, y);if(y != m && a[find(pos(x,y+1))] < tmp[i].val) f[find(pos(x,y+1))] = fa[find(pos(x,y+1))][0] = pos(x, y);}int rt;for(int i = 1; i <= n*m; ++i){if(fa[i][0]) G[fa[i][0]].push_back(i);else rt = i;}dfs(rt);for(int i = 1; i <= n*m; ++i){set<int>::iterator it1, it2;it1 = it2 = col[b[i]].lower_bound(lpos[i]);int pos1 = 0, pos2 = 0;if(it1 != col[b[i]].begin()) pos1 = *--it1;if(it2 != col[b[i]].end()) pos2 = *it2;modifynode(lpos[i], lpos[i], 1);if(pos1) modifynode(lpos[i], pos1, -1);if(pos2) modifynode(pos2, lpos[i], -1);if(pos1 && pos2) modifynode(pos2, pos1, 1);col[b[i]].insert(lpos[i]);}a[0] = 1e9+7;while(q--){int op, x, y, k;read(op, y, x, k);if(op == 1){modifycol(pos(x,y), k);}if(op == 2){int now = pos(x, y);if(k < a[now]){puts("0");continue;}for(int i = 20; ~i; --i)if(a[fa[now][i]] <= k) now = fa[now][i];printf("%d\n", queryint(lpos[now], rpos[now]));}}return 0;
}