免费做翻页页面的网站/媒体公关

当一个人看见星空，就再无法忍受黑暗
为了点亮渐渐沉寂的星空
不想就这样退役

一定不会鸽の坑
. 一本通提高篇
. 算竞进阶
. CDQ & 整体二分
. 平衡树
. LCT
. 字符串
. 随机化算法
. 图论
. 双向BFS
. 组合数学
. 同余

UNFINISHED LIST

提高

道路和航线
汽车加油行驶问题
皇宫看守
旅游规划
凸多边形的划分
跳跳棋
叶子的颜色
骑士
旅行问题
股票交易

算竞

Picnic Planning
天天爱跑步
疫情控制
岛屿
Freda的传呼机

图论

Sightseeing Trip

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 107;#define FALSE_RESULT printf("No solution.")int g[N][N], path[N][N], ans[N], top, dis[N][N];
inline void GetPath(int x, int y){if(!path[x][y]) return;GetPath(x, path[x][y]);ans[++top] = path[x][y];GetPath(path[x][y], y);
}
int main(){
//FileOpen();int n, m;io >> n >> m;R(i,1,n){R(j,1,n){if(i != j)g[i][j] = dis[i][j] = 0x3f3f3f3f;}}R(i,1,m){int u, v, w;io >> u >> v >> w;if(w < g[u][v]){g[u][v] = g[v][u] = dis[u][v] = dis[v][u] = w;}}long long minLen = 9223372036854775807;R(k,1,n){R(i,1,k - 1){R(j,i + 1,k - 1){if(minLen > (long long)dis[i][j] + g[j][k] + g[k][i]){minLen = (long long)dis[i][j] + g[j][k] + g[k][i];top = 1;ans[top] = i;GetPath(i ,j);ans[++top] = j;ans[++top] = k;}}}R(i,1,n){R(j,1,n){if(dis[i][j] > dis[i][k] + dis[k][j]){dis[i][j] = dis[i][k] + dis[k][j];path[i][j] = k;}} }}if(minLen >= 0x3f3f3f3f){FALSE_RESULT;}else{R(i,1,top){printf("%d ", ans[i]);}}//D_e(minLen);return 0;
}

孤岛营救问题

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}
#include <queue>
const int N = 13;struct node{int x, y, step, s;
};
queue<node> q;
int n, m, P, K, S;
int mp[N][N][N][N], key[N][N][N], tot[N][N];
bool vis[N][N][1073];int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
inline int BFS(){int s0 = 0;R(i,1,tot[1][1]) s0 |= 1 << (key[1][1][i] - 1);vis[1][1][s0] = 1;q.push((node){ 1, 1, 0, s0});while(!q.empty()){int x = q.front().x, y = q.front().y, s0 = q.front().s, step = q.front().step;q.pop();R(k,0,3){int s = s0, fx = x + dx[k], fy = y + dy[k];if(fx < 1 || fx > n || fy < 1 || fy > m) continue;if(mp[x][y][fx][fy] == -1) continue;if(mp[x][y][fx][fy] != 0)if(!(s & (1 << (mp[x][y][fx][fy] - 1)))) continue; if(fx == n && fy == m) return step + 1; // I don' t know why, but if I add 2, the answer is right R(i,1,tot[fx][fy]){s |= (1 << (key[fx][fy][i] - 1));}if(vis[fx][fy][s]) continue;vis[fx][fy][s] = 1;q.push((node){ fx, fy, step + 1, s});}}return -1;
}
int main(){
//FileOpen();io >> n >> m >> P >> K;R(i,1,K){int X1, X2, Y1, Y2, col;io >> X1 >> Y1 >> X2 >> Y2 >> col;mp[X1][Y1][X2][Y2] = mp[X2][Y2][X1][Y1] = (col == 0 ? -1 : col);}io >> S;R(i,1,S){int X, Y, col;io >> X >> Y >> col;key[X][Y][++tot[X][Y]] = col;}printf("%d", BFS());return 0;
}

架设电话线

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 2007;int n, m, K;
struct Edge{int nxt, pre, w;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v, int w){e[++cntEdge] = (Edge){ head[u], v, w}, head[u] = cntEdge;
}#include <queue>
struct nod{int x, w;bool operator < (const nod &com) const{return w < com.w;}
};
priority_queue<nod> q;
int dis[N];inline bool Check(int maxDis){R(i,1,n) dis[i] = 0x3f3f3f3f;dis[1] = 0;q.push((nod){ 1, dis[1]});while(!q.empty()){int u = q.top().x, w = q.top().w;q.pop();if(w != dis[u]) continue;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre, val = (e[i].w > maxDis);if(dis[v] > dis[u] + val){dis[v] = dis[u] + val;q.push((nod){ v, dis[v]});}}}return dis[n] <= K;
}int main(){
//FileOpen();io >> n >> m >> K;int maxx = 0;R(i,1,m){int u, v, w;io >> u >> v >> w;add(u, v, w);add(v, u, w);maxx = max(maxx, w);}int l = 0, r = maxx, ans = -1;while(l <= r){int mid = (l + r) >> 1;if(Check(mid)){r = mid - 1;ans = mid;}else{l = mid + 1;}}printf("%d", ans == -1 ? -1 : ans);return 0;
} 

最优贸易

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 100007;
const int M = 500007;int n, m;struct Edge{int nxt, pre;
}e[M << 1], e2[M << 1];
int head[N], cntEdge;
int head2[N], cntEdge2;
inline void add(int u, int v){e[++cntEdge] = (Edge) { head[u], v}, head[u] = cntEdge;
}
inline void add2(int u, int v){e2[++cntEdge2] = (Edge) { head2[u], v}, head2[u] = cntEdge2;
}int dis1[N], dis2[N], vis[N];
int q[N], top;
int val[N];
inline void SPFA(){R(i,1,n) dis1[i] = 0x3f3f3f3f;vis[1] = true;q[++top] = 1;while(top){int u = q[top--];vis[u] = false;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(dis1[v] > min(dis1[u], val[v])){dis1[v] = min(dis1[u], val[v]);if(!vis[v]){vis[v] = true;q[++top] = v;}}}}
}
inline void SPFA_2(){R(i,1,n) dis2[i] = -0x3f3f3f3f;R(i,1,n) vis[i] = false;dis2[n] = 0;vis[n] = true;q[++top] = n;while(top){int u = q[top--];vis[u] = false;for(register int i = head2[u]; i; i = e2[i].nxt){int v = e2[i].pre;if(dis2[v] < max(dis2[u], val[v])){dis2[v] = max(dis2[u], val[v]);if(!vis[v]){vis[v] = true;q[++top] = v;}}}}
}
int main(){io >> n >> m;R(i,1,n){io >> val[i];}R(i,1,m){int u, v, type;io >> u >> v >> type;if(type == 1){add(u, v);add2(v, u); }else{add(u, v);add(v, u);add2(u, v);add2(v, u);}}SPFA();SPFA_2();int ans = 0;R(i,1,n){ans = max(ans, dis2[i] - dis1[i]);}printf("%d", ans);return 0;
}

[USACO11JAN]道路和飞机Roads and Planes

以前一直以为Dij不能处理负边，其实只是不能用于负权环

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}
#include<queue>template <typename T> inline void read(T &x){char c=getchar(); x=0; bool f=1;while(!isdigit(c)) f= !f||c=='-' ? 0:1,c=getchar();while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();x= f? x:-x;
}const int N = 25007;
const int M = 150007;int n, m1, m2, st;
struct Edge{int nxt, pre, from, w;
}e[M];
int head[N], cntEdge;
inline void add(int u, int v, int w){e[++cntEdge] = (Edge){ head[u], v, u, w}, head[u] = cntEdge;
}
int dfn[N], low[N], dfnIndex, scc[N], sccIndex;
int sta[N], top;
inline void Tarjan(int u){dfn[u] = low[u] = ++dfnIndex;sta[++top] = u;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(!dfn[v]){Tarjan(v);low[u] = min(low[u], low[v]);}else if(!scc[v]){low[u] = min(low[u], dfn[v]);}}if(low[u] == dfn[u]){++sccIndex;do{scc[sta[top]] = sccIndex;}while(sta[top--] != u);}
}struct nod{int x, w;bool operator < (const nod &com) const{if(scc[x] != scc[com.x]) return scc[x] < scc[com.x];return w > com.w;}
};
int dis[N];
priority_queue<nod> q;
inline void Dijkstra(){R(i,1,n) dis[i] = 0x3f3f3f3f;dis[st] = 0;q.push((nod){ st, dis[st]});while(!q.empty()){int u = q.top().x, w = q.top().w;q.pop();if(w != dis[u]) continue;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(dis[v] > dis[u] + e[i].w){dis[v] = dis[u] + e[i].w;q.push((nod){ v, dis[v]});}}}
}int main(){
//FileOpen();
//FileSave();io >> n >> m1 >> m2 >> st;R(i,1,m1){int u, v, w;io >> u >> v >> w;add(u, v, w);add(v, u, w);}R(i,1,m2){int u, v, w;io >> u >> v >> w;add(u, v, w);}R(i,1,n){if(!dfn[i])Tarjan(i);}Dijkstra();R(i,1,n){if(dis[i] == 0x3f3f3f3f)printf("NO PATH\n");elseprintf("%d\n", dis[i]);}return 0;
}

拓扑排序判正环

Sorting It All Out

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}
#include<queue>template <typename T> inline void read(T &x){char c=getchar(); x=0; bool f=1;while(!isdigit(c)) f= !f||c=='-' ? 0:1,c=getchar();while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();x= f? x:-x;
}const int N = 25007;
const int M = 150007;int n, m1, m2, st;
struct Edge{int nxt, pre, from, w;
}e[M];
int head[N], cntEdge;
inline void add(int u, int v, int w){e[++cntEdge] = (Edge){ head[u], v, u, w}, head[u] = cntEdge;
}
int dfn[N], low[N], dfnIndex, scc[N], sccIndex;
int sta[N], top;
inline void Tarjan(int u){dfn[u] = low[u] = ++dfnIndex;sta[++top] = u;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(!dfn[v]){Tarjan(v);low[u] = min(low[u], low[v]);}else if(!scc[v]){low[u] = min(low[u], dfn[v]);}}if(low[u] == dfn[u]){++sccIndex;do{scc[sta[top]] = sccIndex;}while(sta[top--] != u);}
}struct nod{int x, w;bool operator < (const nod &com) const{if(scc[x] != scc[com.x]) return scc[x] < scc[com.x];return w > com.w;}
};
int dis[N];
priority_queue<nod> q;
inline void Dijkstra(){R(i,1,n) dis[i] = 0x3f3f3f3f;dis[st] = 0;q.push((nod){ st, dis[st]});while(!q.empty()){int u = q.top().x, w = q.top().w;q.pop();if(w != dis[u]) continue;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(dis[v] > dis[u] + e[i].w){dis[v] = dis[u] + e[i].w;q.push((nod){ v, dis[v]});}}}
}int main(){
//FileOpen();
//FileSave();io >> n >> m1 >> m2 >> st;R(i,1,m1){int u, v, w;io >> u >> v >> w;add(u, v, w);add(v, u, w);}R(i,1,m2){int u, v, w;io >> u >> v >> w;add(u, v, w);}R(i,1,n){if(!dfn[i])Tarjan(i);}Dijkstra();R(i,1,n){if(dis[i] == 0x3f3f3f3f)printf("NO PATH\n");elseprintf("%d\n", dis[i]);}return 0;
}

[APIO2010]巡逻

分情况讨论。
在K为2时将直径赋-1
直径有一种省空间写法

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 100007;int n;
struct Edge{int nxt, pre, w;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v, int w) {e[++cntEdge] = (Edge){ head[u], v, w}, head[u] = cntEdge;
}int s1[N], s2[N]; // the two ends of the Dir
int maxPos, maxDis;
inline int DFS(int u, int father){int mx1 = 0, mx2 = 0;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;int val = e[i].w + DFS(v, u);if(val > mx1){mx2 = mx1, mx1 = val;s2[u] = s1[u], s1[u] = i;}else if(val > mx2){mx2 = val;s2[u] = i;}}if(mx1 + mx2 > maxDis){maxDis = mx1 + mx2;maxPos = u;}return mx1;
} int main(){int K;io >> n >> K;R(i,2,n){int u, v;io >> u >> v;add(u, v, 1);add(v, u, 1);}DFS(1, 0);
//  D_e(maxPos);
//      for(register int i = s1[maxPos]; i; i = s1[e[i].pre]) D_e(e[i].pre);
//      D_e_Line;
//      for(register int i = s2[maxPos]; i; i = s1[e[i].pre]) D_e(e[i].pre);
//  D_e_Line;if(K == 1){printf("%d", (n << 1) - maxDis - 1);return 0;}else{int D1 = maxDis;maxDis = 0;for(register int i = s1[maxPos]; i; i = s1[e[i].pre]) e[i].w = e[i + 1].w = -1;for(register int i = s2[maxPos]; i; i = s1[e[i].pre]) e[i].w = e[i + 1].w = -1;DFS(1, 0);printf("%d", (n << 1) - maxDis - D1);}return 0;
} 
/*
8 1 
1 2 
3 1 
3 4 
5 3 
7 5 
8 5 
5 6 
*/
/*
8 1
1 2
1 3
3 7
3 6
2 5
2 4
4 8
*/
/*
6 1
1 2
2 3
3 4
3 6
1 5
*/

雨天的尾巴

线段树合并，开60倍空间

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 100007;int n, m;
struct Edge{int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge) { head[u], v}, head[u] = cntEdge;
}int dfn[N], dfnIndex, top[N], siz[N], dep[N], fa[N], son[N];
inline void DFS_First(int u, int father){fa[u] = father, siz[u] = 1, dep[u] = dep[father] + 1;for(register int i =  head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;DFS_First(v, u);siz[u] += siz[v];if(siz[v] > siz[son[u]]) son[u] = v;}
}
inline void DFS_Second(int u, int TP){top[u] = TP, dfn[u] = ++dfnIndex;if(!son[u]) return;DFS_Second(son[u], TP);for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v != son[u] && v != fa[u])DFS_Second(v, v);}
}
inline int LCA(int x, int y){while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) Swap(x, y);x = fa[top[x]];}return dep[x] < dep[y] ? x : y;
}int rt[N];struct Tree{int l, r, pos, val;
}t[N * 60];
int treeIndex;
#define ls t[rt].l
#define rs t[rt].r
#define lson t[rt].l, l, mid
#define rson t[rt].r, mid + 1, r
inline void Pushup(int rt){if(t[ls].val < t[rs].val){t[rt].val = t[rs].val;t[rt].pos = t[rs].pos;}else{t[rt].val = t[ls].val;t[rt].pos = t[ls].pos;}
}
inline void Updata(int &rt, int l, int r, int x, int val){if(!rt) rt = ++treeIndex;if(l == r){t[rt].val += val;t[rt].pos = l;return;}int mid = (l + r) >> 1;if(x <= mid)Updata(lson, x, val);elseUpdata(rson, x, val);Pushup(rt);
}
inline int Merge(int x, int y, int l, int r){if(!x || !y) return x | y;if(l == r){t[x].val += t[y].val;t[x].pos = l;return x;}int mid = (l + r) >> 1;t[x].l = Merge(t[x].l, t[y].l, l, mid);t[x].r = Merge(t[x].r, t[y].r, mid + 1, r);Pushup(x);return x;
}int ans[N];int f[N];
inline void DFS(int u, int father){for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;DFS(v, u);rt[u] = Merge(rt[u], rt[v], 1, N - 1);}if(t[rt[u]].val){ans[u] = t[rt[u]].pos;}
}
int main(){
//FileOpen();io >> n >> m;R(i,2,n){int u, v;io >> u >> v;add(u, v);add(v, u);}DFS_First(1, 0);DFS_Second(1, 1);R(i,1,m){int x, y, col;io >> x >> y >> col;int lca = LCA(x, y);Updata(rt[x], 1, N - 1, col, 1);Updata(rt[y], 1, N - 1, col, 1);Updata(rt[lca], 1, N - 1, col, -1);if(lca != 1){Updata(rt[fa[lca]], 1, N - 1, col, -1);}}DFS(1, 0);R(i,1,n){printf("%d\n", ans[i]);}return 0;
}

次小生成树

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP Max(ATP a, ATP b){return a > b ? a : b;
}
template<typename ATP>inline ATP Min(ATP a, ATP b){return a < b ? a : b;
}
template<typename ATP>inline ATP Abs(ATP a){return a < 0 ? -a : a;
}const int N = 100007;
const int M = 300007;int n, m; 
struct Node{int x, y, w, tag;bool operator < (const Node &com) const{return w < com.w;}
}a[M];
struct Edge{int nxt, pre; long long w;
}e[M << 1];
int head[N], cntEdge;
inline void add(int u, int v, int w){e[++cntEdge] = (Edge){ head[u], v, w}, head[u] = cntEdge;
}long long MST;
int f[N];
inline int Find(int x){return x == f[x] ? x : f[x] = Find(f[x]);
}
inline void Kruskal(){int tot = 1;R(i,1,n) f[i] = i;sort(a + 1, a + m + 1);R(i,1,m){int p = Find(a[i].x), q = Find(a[i].y);if(p != q){f[p] = q;MST += a[i].w;a[i].tag = true;if(++tot >= n) return;}}
}long long wSon[N];
int son[N], fa[N], siz[N], dep[N];
inline void DFS_First(int u, int father){dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v ==  father) continue;DFS_First(v, u);siz[u] += siz[v];if(siz[v] > siz[son[u]]){son[u] = v;wSon[u] = e[i].w;}}
}
int top[N], dfn[N], dfnIndex, rnk[N];
inline void DFS_Second(int u, int TP, int w){dfn[u] = ++dfnIndex, top[u] = TP, rnk[dfnIndex] = w;if(!son[u]) return;DFS_Second(son[u], TP, wSon[u]);for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v != fa[u] && v != son[u])DFS_Second(v, v, e[i].w);}
}#define ls rt << 1
#define rs rt << 1 | 1
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
struct Tree{int mx,sc;
}t[M << 2];
inline void Pushup(int rt){t[rt].mx = Max(t[ls].mx, t[rs].mx);t[rt].sc = Max(t[rt].mx != t[ls].mx ? t[ls].mx : t[ls].sc, t[rt].mx != t[rs].mx ? t[rs].mx : t[rs].sc);
}
inline void Build(int rt, int l, int r){if(l == r){t[rt].mx = rnk[l];t[rt].sc = -1;return;}int mid = (l + r) >> 1;Build(lson), Build(rson);Pushup(rt);
}
inline Tree Query(int rt, int l, int r, int L, int R){if(L <= l && r <= R) return t[rt];int mid = (l + r) >> 1;Tree tmp_1, tmp_2, res;tmp_1.mx = tmp_1.sc = tmp_2.mx = tmp_2.sc = 0;if(L <= mid) tmp_1 = Query(lson, L, R);if(mid < R) tmp_2 = Query(rson, L, R);res.mx = Max(tmp_1.mx, tmp_2.mx);res.sc = Max(tmp_1.mx != res.mx ? tmp_1.mx : tmp_1.sc, tmp_2.mx != res.mx ? tmp_2.mx : tmp_2.sc);return res;
}inline int QueryPath(int u, int v, int w){int sum = 0;while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]]) Swap(u, v);Tree tmp = Query(1, 1, n, dfn[top[u]], dfn[u]);sum = Max(sum, w != tmp.mx ? tmp.mx : tmp.sc);u = fa[top[u]];}if(u == v) return sum;if(dep[u] < dep[v]) Swap(u, v);Tree tmp = Query(1, 1, n, dfn[v] + 1, dfn[u]);return Max(sum, w != tmp.mx ? tmp.mx : tmp.sc);;
}int sta[M << 1], topp;
int main(){
//FileOpen();io >> n >> m;R(i,1,m){int u, v, w;io >> u >> v >> w;a[i] = (Node){ u, v, w, 0};}Kruskal();R(i,1,m){if(a[i].tag == true){add(a[i].x, a[i].y, a[i].w);add(a[i].y, a[i].x, a[i].w);}elsesta[++topp] = i;}DFS_First(1, 0);DFS_Second(1, 0, 0);Build(1, 1, n);int sum = 0x7fffffff;R(i,1,topp){sum = Min(sum, a[sta[i]].w - QueryPath(a[sta[i]].x, a[sta[i]].y, a[sta[i]].w));}printf("%lld", MST + sum);return 0;
}

舞动的夜晚

网络流模板，开空间玄学，若流量非0且不属于合法环，则非法

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP Max(ATP a, ATP b){return a > b ? a : b;
}
template<typename ATP>inline ATP Min(ATP a, ATP b){return a < b ? a : b;
}
template<typename ATP>inline ATP Abs(ATP a){return a < 0 ? -a : a;
}const int N = 500007;
const int M = 2000007;int S = 0, T;
struct Edge{int nxt, pre, w;
}e[M], e2[M];
int head[N], head2[N], cntEdge = 1, cntEdge2 = 1;
inline void add(int u, int v, int w){e[++cntEdge] = (Edge){ head[u], v, w}, head[u] = cntEdge;
}
inline void add2(int u, int v){e2[++cntEdge2] = (Edge){ head2[u], v}, head2[u] = cntEdge2;
}
inline void Add(int u, int v){add(u, v, 1);add(v, u, 0);
}int q[N], h[N];
inline bool BFS(){int t = 0, w = 1;Fill(h, -1);h[S] = 0, q[0] = S;while(t != w){int u = q[t++];for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(e[i].w && h[v] == -1){h[v] = h[u] + 1;q[w++] = e[i].pre;}}}return h[T] != -1;
}
inline int DFS(int u, int f){if(u == T) return f;int w, used = 0;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(h[v] == h[u] + 1){w = DFS(v, Min(f - used, e[i].w));e[i].w -= w, e[i ^ 1].w += w;used += w;if(used == f) return f;}}if(!used) h[u] = -1;return used;
}
inline int Dinic(){int sum = 0;while(BFS()){sum += DFS(S, 0x7fffffff);}return sum;
}int dfn[N], low[N], dfnIndex, scc[N], sccIndex;
int sta[N], top;
inline void Tarjan(int u){dfn[u] = low[u] = ++dfnIndex;sta[++top] = u;for(register int i = head2[u]; i; i = e2[i].nxt){int v = e2[i].pre;if(!dfn[v]){Tarjan(v);low[u] = Min(low[u], low[v]);}else if(!scc[v]){low[u] = Min(low[u], dfn[v]);}}if(dfn[u] == low[u]){++sccIndex;do{scc[sta[top]] = sccIndex;}while(sta[top--] != u);}
}
int ans[N];
int happy[N][2];
int main(){
//FileOpen();int n1, n2, m;io >> n1 >> n2 >> m;T = n1 + n2 + 1; R(i,1,m){int u, v;io >> u >> v;happy[i][0] = u, happy[i][1] = v + n1;Add(u, n1 + v);}R(i,1,n1) Add(S, i);R(i,1,n2) Add(n1 + i, T);Dinic();R(i,2,cntEdge){if(e[i].w){add2(e[i ^ 1].pre, e[i].pre);}}R(i,S,T){if(!dfn[i]){Tarjan(i);}}R(i,1,m){if(scc[happy[i][0]] != scc[happy[i][1]] && e[i << 1].w != 0){ans[++top] = i;}}printf("%d\n", top);R(i,1,top){printf("%d ", ans[i]);}return 0;
}

创世纪

基环树DP，攻的当受的儿子，\(f\)表选，\(g\)表不选。并查集维护攻受关系。若有环则记录，DP受的后把它当祖宗，再DP攻的。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n")
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP Max(ATP a, ATP b){return a > b ? a : b;
}
template<typename ATP>inline ATP Min(ATP a, ATP b){return a < b ? a : b;
}
template<typename ATP>inline ATP Abs(ATP a){return a < 0 ? -a : a;
}const int N = 1000007;int n, totCircle;
int ans, root;
int f[N], g[N], A[N], B[N];
struct Edge{int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge){ head[u], v}, head[u] = cntEdge;
}
int fa[N];
inline int Find(int x){return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
inline void DFS(int u){int t = 0x7fffffff;g[u] = 0;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v != root) DFS(v);g[u] += max(f[v], g[v]);t = min(t, max(f[v], g[v]) - g[v]);}f[u] = g[u] + 1 - t;
}
int main(){
//FileOpen();io >> n;R(i,1,n) fa[i] = i;R(i,1,n){int j;io >> j;int p = Find(i), q = Find(j);if(p != q){add(j, i);fa[q] = p;}else{A[++totCircle] = j, B[totCircle] = i;}}R(i,1,totCircle){DFS(A[i]), root = A[i];DFS(B[i]);int tmp = f[B[i]];f[A[i]] = g[A[i]] + 1;DFS(B[i]);ans += Max(tmp, g[B[i]]);}printf("%d",ans);return 0;
}

银河

因为只有\(0/1\)两种权值，缩点后拓扑

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n")
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP Max(ATP a, ATP b){return a > b ? a : b;
}
template<typename ATP>inline ATP Min(ATP a, ATP b){return a < b ? a : b;
}
template<typename ATP>inline ATP Abs(ATP a){return a < 0 ? -a : a;
}const int N = 100007;int n, m;
struct Edge{int nxt, pre, w;
}e[N << 2];
int head[N], cntEdge;
inline void add(int u, int v, int w){e[++cntEdge] = (Edge){ head[u], v, w}, head[u] = cntEdge;
}int dfn[N], low[N], dfnIndex;
int sta[N], top;
int scc[N], sccIndex;
inline void Tarjan(int u){dfn[u] = low[u] = ++dfnIndex;sta[++top] = u;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(!dfn[v]){Tarjan(v);low[u] = min(low[u], low[v]);} else if(!scc[v]){low[u] = min(low[u], dfn[v]);}}if(low[u] == dfn[u]){++sccIndex;do{scc[sta[top]] = sccIndex;}while(sta[top--] != u);}
}
Edge E[N << 2];
int Head[N], CntEdge;
int In[N];
inline void Add(int u, int v, int w){E[++CntEdge] = (Edge){ Head[u], v, w}, Head[u] = CntEdge;
}
inline bool ReBuild(){R(u,1,n){for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(scc[u] == scc[v]){if(e[i].w == 1) return false;}else{Add(scc[u], scc[v], e[i].w);++In[scc[v]];}}}return true;
}
int q[N], Dis[N];
inline void TopoSort(){R(i,1,sccIndex){if(!In[i]){q[++top] = i;Dis[i] = 1;}}while(top){int u = q[top--];for(register int i = Head[u]; i; i = E[i].nxt){int v = E[i].pre;Dis[v] = max(Dis[v], Dis[u] + E[i].w);if(--In[v] == 0){q[++top] = v;}}}
}
int main(){io >> n >> m;R(i,1,m){int opt, a, b;io >> opt >> a >> b;if(opt == 1){add(a, b, 0);add(b, a, 0);}else if(opt == 2){add(a, b, 1);if(a == b){printf("-1");return 0;}}else if(opt == 3){add(b, a, 0);}else if(opt == 4){add(b, a, 1);if(a == b){printf("-1");return 0;}}else{add(a, b, 0);}}R(i,1,n){if(!dfn[i]){Tarjan(i);}}if(ReBuild() == false){printf("-1");}else{TopoSort();long long ans = 0;R(i,1,n){ans += Dis[scc[i]];}printf("%lld", ans);}return 0;
}

Knights of the Round Table

二分图无奇环，反之亦然
建反图跑点双联通

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n")
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP Max(ATP a, ATP b){return a > b ? a : b;
}
template<typename ATP>inline ATP Min(ATP a, ATP b){return a < b ? a : b;
}
template<typename ATP>inline ATP Abs(ATP a){return a < 0 ? -a : a;
}const int N = 1007;int n, m;
struct Edge{int nxt, pre;
}e[N * N];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge){ head[u], v}, head[u] = cntEdge;
}int vis[N];int color[N];
int tmp[N];
int dfn[N], dfnIndex, low[N], scc[N], sccIndex;
int sta[N], top;
inline bool OddCircle(int u, int col){color[u] = col;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(scc[v] == sccIndex){if(color[v] && color[v] == color[u]) return true;if(!color[v] && OddCircle(v, -col)) return true;}}return false;
}
//inline void Tarjan(int u, int father){
//  dfn[u] = low[u] = ++dfnIndex;
//  sta[++top] = u;
//  int sons = 0;
//  for(register int i = head[u]; i; i = e[i].nxt){
//      int v = e[i].pre;
//      if(v == father) continue;
//      if(!dfn[v]){
//          Tarjan(v, u);
//          low[u] = min(low[u], low[v]);
//          if(low[v] >= dfn[u]){
//              ++sons;
//              int tot = 0;
//              if(u != root || sons > -1){
//                  /*
//                      I think I should write sons > 1,
//                      but if I ignore this judgement, the answer is right.
//                      I still do not understand.
//                  */
//                  ++sccIndex;
//                  do{
//                      scc[sta[top]] = sccIndex;
//                      tmp[++tot] = sta[top];
//                  }while(sta[top--] != v); // not u
//                  tmp[++tot] = u;
//                  if(tot < 3){
//                      tot = 0;
//                      continue;
//                  }
//                  R(j,1,n) color[j] = 0;
//                  if(OddCircle(u, 1) == true){
//                      while(tot){
//                          vis[tmp[tot]] = 1;
//                          --tot;
//                      }
//                  }
//              }
//          }
//          
//      }
//      else if(!scc[v]){
//          low[u] = min(low[u], dfn[v]);
//      }
//  }
//}
/*Now I understand, my template is wrong,the judgement is only used for the cut vertices 
*/
inline void Tarjan(int u, int father){dfn[u] = low[u] = ++dfnIndex;sta[++top] = u;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;if(!dfn[v]){Tarjan(v, u);low[u] = min(low[u], low[v]);if(low[v] >= dfn[u]){int tot = 0;++sccIndex;do{scc[sta[top]] = sccIndex;tmp[++tot] = sta[top];}while(sta[top--] != v); // not utmp[++tot] = u;if(tot < 3){tot = 0;continue;}R(j,1,n) color[j] = 0;if(OddCircle(u, 1) == true){while(tot){vis[tmp[tot]] = 1;--tot;}}}}else if(!scc[v]){low[u] = min(low[u], dfn[v]);}}
}int mp[N][N];
int main(){
//FileOpen();while(~scanf("%d%d", &n, &m) && n | m){cntEdge = 0;dfnIndex = 0;sccIndex = 0;R(i,1,n){R(j,1,n){mp[i][j] = i == j ? 1 : 0;}}R(i,1,n){vis[i] = 0;head[i] = 0;dfn[i] = 0;low[i] = 0;scc[i] = 0;}R(i,1,m){int u, v;io >> u >> v;mp[u][v] = mp[v][u] = 1;}R(i,1,n){R(j,1,n){if(!mp[i][j]){add(i, j);add(j, i);}}}R(i,1,n){if(!dfn[i]){Tarjan(i, 0);}}int ans = 0;R(i,1,n){ans += (!vis[i]);}printf("%d\n", ans);}return 0;
}

Network

无向图原是可当有向图来缩的，加个爸爸就是了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n")
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP Max(ATP a, ATP b){return a > b ? a : b;
}
template<typename ATP>inline ATP Min(ATP a, ATP b){return a < b ? a : b;
}
template<typename ATP>inline ATP Abs(ATP a){return a < 0 ? -a : a;
}const int N = 100007;
const int M = 400007;struct Edge{int nxt, pre;
}e[M];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge) { head[u], v}, head[u] = cntEdge;
}Edge E[N];
int Head[N], CntEdge;
inline void Add(int u, int v){E[++CntEdge] = (Edge) { Head[u], v}, Head[u] = CntEdge;
}int dfn[N], low[N], dfnIndex, scc[N], sccIndex;
int sta[N], top;
inline void Tarjan(int u, int father){dfn[u] = low[u] = ++dfnIndex;sta[++top] = u;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;if(!dfn[v]){Tarjan(v, u);low[u] = Min(low[u], low[v]);}else if(!scc[v]){low[u] = Min(low[u], dfn[v]);}}if(low[u] == dfn[u]){++sccIndex;do{scc[sta[top]] = sccIndex;}while(sta[top--] != u);}
}namespace UFO{int fa[N];
inline int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);
}}namespace TCP{int top[N], dep[N], fa[N], son[N], siz[N];
inline void DFS_First(int u, int father){dep[u] = dep[father] + 1, siz[u] = 1, fa[u] = father;for(register int i = Head[u]; i; i = E[i].nxt){int v = E[i].pre;if(v == father) continue;DFS_First(v, u);siz[u] += siz[v];if(siz[v] > siz[son[u]]) son[u] = v;}
}
inline void DFS_Second(int u, int TP){top[u] = TP;if(!son[u]) return;DFS_Second(son[u], TP);for(register int i = Head[u]; i; i = E[i].nxt){int v = E[i].pre;if(v != fa[u] && v != son[u])DFS_Second(v, v);}
}
inline int LCA(int x, int y){while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) Swap(x, y);x = fa[top[x]];}return dep[x] < dep[y] ? x : y;
}}int n, m;
int main(){
//FileOpen();int Tasks = 0;while(~scanf("%d%d", &n, &m) && n | m){cntEdge = 0;CntEdge = 0;dfnIndex = 0;sccIndex = 0;R(i,1,n){head[i] = 0;scc[i] = 0;dfn[i] = 0;low[i] = 0;UFO::fa[i] = i;TCP::top[i] = 0;Head[i] = 0;TCP::son[i] = 0;}if(Tasks) putchar('\n');printf("Case %d:\n", ++Tasks);R(i,1,m){int u, v;io >> u >> v;add(u, v);add(v, u);}R(i,1,n){if(!dfn[i])Tarjan(i, 0);}R(u,1,n){for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(scc[u] != scc[v]){Add(scc[u], scc[v]);}}}TCP::DFS_First(1, 0);TCP::DFS_Second(1, 1);int ans = sccIndex - 1, Ques;io >> Ques;while(Ques--){int u, v;io >> u >> v;u = UFO::Find(scc[u]), v = UFO::Find(scc[v]);if(u != v){int lca = TCP::LCA(u, v);while(u != lca){--ans;UFO::fa[u] = lca;u = TCP::fa[u];u = UFO::Find(u);}while(v != lca){--ans;UFO::fa[v] = lca;v = TCP::fa[v];v = UFO::Find(v);}}printf("%d\n", ans);}}return 0;
}

Watchcow

\(vis\)用在边

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n")
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP Max(ATP a, ATP b){return a > b ? a : b;
}
template<typename ATP>inline ATP Min(ATP a, ATP b){return a < b ? a : b;
}
template<typename ATP>inline ATP Abs(ATP a){return a < 0 ? -a : a;
}const int N = 10007;
const int M = 100007;struct Edge{int nxt, pre;
}e[M];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge) { head[u], v}, head[u] = cntEdge;
} int vis[M], tot, path[M];
inline void DFS(int u){for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(!vis[i]){vis[i] = 1;DFS(v);}}path[++tot] = u;
}
int n, m;
int main(){io >> n >> m;R(i,1,m){int u, v;io >> u >> v;add(u, v);add(v, u);}DFS(1);R(i,1,tot){printf("%d\n", path[i]);}return 0;
}

RMQ问题

与众不同

#include <cstdio>
//#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;#endif
using namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 200007;int n;namespace RMQ{int f[N][21], lg[N], bin[21], last[N * 10], a[N], pos[N];
inline void Prepare(){bin[0] = 1;R(i,1,20) bin[i] = bin[i - 1] << 1;R(i,2,n) lg[i] = lg[i >> 1] + 1;
}
inline void Init(){R(i,1,n){io >> a[i];a[i] += 1000000;pos[i] = max(pos[i - 1], last[a[i]] + 1);f[i][0] = i - pos[i] + 1;last[a[i]] = i;}int t = lg[n];R(j,1,t){int maxx = n - bin[j] + 1;R(i,1,maxx){f[i][j] = max(f[i][j - 1], f[i + bin[j - 1]][j - 1]);}}
}
inline int Query(int l, int r){int t = lg[r - l + 1];return max(f[l][t], f[r - bin[t] + 1][t]);
}}int main(){
//FileOpen();
//freopen("1.txt", "w", stdout);int m;io >> n >> m;RMQ::Prepare();RMQ::Init();while(m--){int L, R;io >> L >> R;++L, ++R;
//      int l = L, r = R, P;
//      while(l <= r){
//          int mid = (l + r) >> 1;
//          if(RMQ::pos[mid] <= L){
//              l = mid + 1;
//              P = l;
//          }
//          else
//              r = mid - 1;
//      }int P = lower_bound(RMQ::pos + L, RMQ::pos + R + 1, L) - RMQ::pos;printf("%d\n", min(R - L + 1, max(P - L, RMQ::Query(P, R)))); // false : P - L + 1}return 0;
}

选择客栈

MLE

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <cstdio>
//#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;#endif
using namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 2000007;int n, colorNum;
int col[N]; 
int f[21][N];
inline void Init(){int t = log2(n);R(j,1,t){int maxx = n - (1 << j) + 1;R(i,1,maxx){f[j][i] = min(f[j - 1][i], f[j - 1][i + (1 << j - 1)]);}}
}
inline int Query(int l, int r){int t = log2(r - l + 1);return min(f[t][l], f[t][r - (1 << t) + 1]);
}#include <vector>
vector<int> V[10007];
int main(){
//FileOpen();
//freopen("in2.txt", "r", stdin);int minAfford;io >> n >> colorNum >> minAfford;R(i,1,n){io >> col[i] >> f[0][i];++col[i];V[col[i]].push_back(i);}Init();long long ans = 0;R(i,1,colorNum){int cnt = 1, tot = V[i].size();for(vector<int>::iterator it = V[i].begin() + 1; it != V[i].end(); ++it){if(Query(*(it - 1), *it) <= minAfford){ans += cnt * (tot - cnt);tot -= cnt;cnt = 0;}++cnt;}}printf("%lld", ans);return 0;
}

AC

#include <cstdio>
//#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;#endif
using namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 2000007;int last[N], tot[N], sum[N];
int main(){
//FileOpen();int n, colorNumber, minAfford;int pos;io >> n >> colorNumber >> minAfford;long long ans = 0;R(i,1,n){int col, pri;io >> col >> pri;if(minAfford >= pri) pos = i;if(pos >= last[col]) sum[col] = tot[col];last[col] = i;ans += sum[col];++tot[col];}printf("%lld", ans);return 0;
}

树链剖分

树的统计

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;#endif
using namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 30007; int n;struct Edge{int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge){head[u], v}, head[u] = cntEdge;
}int val[N];int fa[N], siz[N], dep[N], son[N];
inline void DFS_First(int u, int father){dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;DFS_First(v, u);siz[u] += siz[v];if(!son[u] || siz[v] > siz[son[u]]){son[u] = v;}}
}
int dfn[N], dfnIndex, rnk[N], top[N];
inline void DFS_Second(int u, int ancester){top[u] = ancester, dfn[u] = ++dfnIndex, rnk[dfnIndex] = u;if(!son[u]) return;DFS_Second(son[u], ancester);for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v != son[u] && v != fa[u]){DFS_Second(v, v);}}
}#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
int t[N << 2], tmax[N << 2];    
inline void Pushup(int &rt){t[rt] = t[rt << 1] + t[rt << 1 | 1];tmax[rt] = max(tmax[rt << 1], tmax[rt << 1 | 1]);
}
inline void Build(int rt, int l, int r){if(l == r){t[rt] = tmax[rt] = val[rnk[l]];return;}int mid = (l + r) >> 1;Build(lson), Build(rson);Pushup(rt);
}
inline void Change(int rt, int l, int r, int &x, int &w){if(l == r){t[rt] = tmax[rt] = w;return;}int mid = (l + r) >> 1;if(mid >= x)Change(lson, x, w);elseChange(rson, x, w);Pushup(rt);
}
inline int QueryMax(int rt, int l, int r, int L, int R){if(L <= l && r <= R) return tmax[rt];int mid = (l + r) >> 1, maxx = -0x7fffffff; // ！error : init maxx 0 if(mid >= L) maxx = max(maxx, QueryMax(lson, L, R));if(mid < R) maxx = max(maxx, QueryMax(rson, L, R));return maxx;
}
inline int QuerySum(int rt, int l, int r, int L, int R){if(L <= l && r <= R) return t[rt];int mid = (l + r) >> 1, sum = 0;if(mid >= L) sum += QuerySum(lson, L, R);if(mid < R) sum += QuerySum(rson, L, R);return sum;
}inline int QueryPathMax(int x, int y){int maxx = -0x7fffffff; // ! error : init maxx 0while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) Swap(x, y);maxx = max(maxx, QueryMax(1, 1, n, dfn[top[x]], dfn[x]));x = fa[top[x]];}if(dep[x] < dep[y]) Swap(x, y);return max(maxx, QueryMax(1, 1, n, dfn[y], dfn[x]));
}
inline int QueryPathSum(int x, int y){int sum = 0;while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) Swap(x, y);sum += QuerySum(1, 1, n, dfn[top[x]], dfn[x]);x = fa[top[x]];}if(dep[x] < dep[y]) Swap(x, y);return sum + QuerySum(1, 1, n, dfn[y], dfn[x]);
}int main(){
//FileOpen();
//freopen("my.txt", "w", stdout);io >> n;R(i,2,n){int u, v;io >> u >> v;add(u, v);add(v, u);}R(i,1,n){io >> val[i];}DFS_First(1, 0);DFS_Second(1, 1);Build(1, 1, n);int m;io >> m;while(m--){char opt[13]; // !error : opt[6]cin >> (opt + 1);if(opt[4] == 'X'){int u, v;io >> u >> v;printf("%d\n", QueryPathMax(u, v));}else if(opt[4] == 'M'){int u, v;io >> u >> v;printf("%d\n", QueryPathSum(u, v));}else{int x, w;io >> x >> w;Change(1, 1, n, dfn[x], w); // ! error : dfn[x] not x}}return 0;
}

树上操作

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() freopen("out.txt", "w", stdout) ;#endif
using namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 100007;
struct Edge{int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge){ head[u], v}, head[u] = cntEdge;
}int siz[N], son[N], fa[N], dep[N];
inline void DFS_First(int u, int father){fa[u] = father, siz[u] = 1, dep[u] = dep[father] + 1;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;DFS_First(v, u);siz[u] += siz[v];if(!son[u] || siz[v] > siz[son[u]])son[u] = v;}
}
int dfn[N], dfnIndex, top[N], rnk[N];
inline void DFS_Second(int u, int ancester){dfn[u] = ++dfnIndex, top[u] = ancester, rnk[dfnIndex] = u;if(!son[u]) return;DFS_Second(son[u], ancester);for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v != son[u] && v != fa[u])DFS_Second(v, v);}
}int n, val[N];#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
long long t[N << 2], tag[N << 2];
inline void Pushup(int &rt){t[rt] = t[rt << 1] + t[rt << 1 | 1];
}
inline void Pushdown(int &rt, int l, int r){if(!tag[rt]) return;int mid = (l + r) >> 1;tag[rt << 1] += tag[rt];tag[rt << 1 | 1] += tag[rt];t[rt << 1] += (mid - l + 1) * tag[rt];t[rt << 1 | 1] += (r - mid) * tag[rt];tag[rt] = 0;
}
inline void Build(int rt, int l, int r){if(l == r){t[rt] = val[rnk[l]];return;}int mid = (l + r) >> 1;Build(lson), Build(rson);Pushup(rt);
}
//inline void Change(int rt, int l, int r, int &x, int &w){
//  if(l == r){
//      t[rt] += w;
//      return;
//  }Pushdown(rt, l, r);
//  int mid = (l + r) >> 1;
//  if(mid >= l)
//      Change(lson, x, w);
//  else
//      Change(rson, x, w);
//  Pushup(rt);
//}
inline void Updata(int rt, int l, int r, int L, int R, long long &w){if(L <= l && r <= R){t[rt] += (r - l + 1) * w;tag[rt] += w;return;}Pushdown(rt, l, r);int mid = (l + r) >> 1;if(mid >= L) Updata(lson, L, R, w);if(mid < R) Updata(rson, L, R, w);Pushup(rt);
}
inline long long Query(int rt, int l, int r, int &L, int &R){if(L <= l && r <= R) return t[rt];Pushdown(rt, l, r);int mid = (l + r) >> 1;long long sum = 0;if(mid >= L) sum += Query(lson, L, R);if(mid < R) sum += Query(rson, L, R);return sum;
}inline long long QueryPath(int x, int y){long long sum = 0;while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) Swap(x, y);sum += Query(1, 1, n, dfn[top[x]], dfn[x]);x = fa[top[x]];}if(dep[x] < dep[y]) Swap(x, y);return sum + Query(1, 1, n, dfn[y], dfn[x]);
}// It seems that the bug is from opt 2
int main(){
//FileOpen();
//FileSave();int m;io >> n >> m;R(i,1,n){io >> val[i];} R(i,2,n){int u, v;io >> u >> v;add(u, v);add(v, u);}   DFS_First(1, 0);DFS_Second(1, 1);Build(1, 1, n);while(m--){int opt;io >> opt;if(opt == 1){int x;long long w;io >> x >> w;//Change(1, 1, n, dfn[x], w);/*I do not understand. It' s error.But if the code below is right.*/Updata(1, 1, n, dfn[x], dfn[x], w); // use long long}else if(opt == 2){int x;long long w;io >> x >> w;Updata(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, w);}else{int x;io >> x;printf("%lld\n", QueryPath(1, x));}}return 0;
} 
/*
5 999
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
3 2
3 3
1 1 9
3 4
3 5*/
/*
9
4
7
13
18
*/

染色

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
//#define TIME() Debug("\nTime: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 100007;int n;
int colorPre[N];struct Edge{int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge){ head[u], v}, head[u] = cntEdge;
}int son[N], fa[N], siz[N], dep[N];
inline void DFS_First(int u, int father){siz[u] = 1, dep[u] = dep[father] + 1, fa[u] = father;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;DFS_First(v, u);siz[u] += siz[v];if(!son[u] || siz[v] > siz[son[u]])son[u] = v;}
}
int dfn[N], dfnIndex, top[N], rnk[N];
inline void DFS_Second(int u, int TP){top[u] = TP, dfn[u] = ++dfnIndex, rnk[dfnIndex] = u;if(!son[u]) return;DFS_Second(son[u], TP);for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v != son[u] && v != fa[u])DFS_Second(v, v);}
}#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1
int t[N << 2], tag[N << 2], col[N];
inline void Pushup(int &rt, int &mid){t[rt] = t[ls] + t[rs] - (col[mid] == col[mid + 1]);
}
inline void Pushdown(int &rt, int mid){tag[ls] = tag[rs] = col[mid] = col[mid + 1] = tag[rt];t[ls] = t[rs] = 1;tag[rt] = 0;
}
inline void Build(int rt, int l, int r){if(l == r){t[rt] = 1;col[l] = colorPre[rnk[l]];return;}int mid = (l + r) >> 1;Build(lson), Build(rson);Pushup(rt, mid);
}
inline void Updata(int rt, int l, int r, int &L, int &R, int &w){if(L <= l && r <= R){t[rt] = 1;col[l] = col[r] = tag[rt] = w;return;}int mid = (l + r) >> 1;if(tag[rt]) Pushdown(rt, mid);if(L <= mid) Updata(lson, L, R, w);if(R > mid) Updata(rson, L, R, w);Pushup(rt, mid);
}
inline int Query(int rt, int l, int r, int L, int R){if(L <= l && r <= R) return t[rt];int mid = (l + r) >> 1;int sum = 0;if(tag[rt]) Pushdown(rt, mid);if(L <= mid) sum += Query(lson, L, R);if(R > mid) sum += Query(rson, L, R);if(L <= mid && R > mid && col[mid] == col[mid + 1]) --sum;return sum;
}inline void PathUpdata(int x, int y, int w){while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) Swap(x, y);Updata(1, 1, n, dfn[top[x]], dfn[x], w);x = fa[top[x]];}if(dep[x] < dep[y]) Swap(x, y);Updata(1, 1, n, dfn[y], dfn[x], w);
}
inline int PathQuery(int x, int y){int sum = 0;
//  while(top[x] != top[y]){
//      if(dep[top[x]] < dep[top[y]]) Swap(x, y);
//      sum += Query(1, 1, n, dfn[top[x]], dfn[x]);
//      if(col[dfn[top[x]]] == col[dfn[fa[top[x]]]]) --sum;
//      x = fa[top[x]];
//  }
//  if(dep[x] < dep[y]) Swap(x, y);
//  sum += Query(1, 1, n, dfn[y], dfn[x]);
/*Though it seems will be quicker in this way, but it cannot really count the real parts with the same color.
*/int tmpX = x, tmpY = y;while(top[x] != top[y]) {if(dep[top[x]] < dep[top[y]]) swap(x, y);sum += Query(1, 1, n, dfn[top[x]], dfn[x]);x = fa[top[x]];}if(dep[x] < dep[y]) swap(x, y);sum += Query(1, 1, n, dfn[y], dfn[x]);x = tmpX, y = tmpY;while(top[x] != top[y]) {if(dep[top[x]] < dep[top[y]]) swap(x, y);if(col[dfn[top[x]]] == col[dfn[fa[top[x]]]]) --sum;x = fa[top[x]];}return sum;
}int main(){
//FileOpen();
//FileSave();int m;io >> n >> m;R(i,1,n) io >> colorPre[i];R(i,2,n){int u, v;io >> u >> v;add(u, v);add(v, u);}DFS_First(1, 0);DFS_Second(1, 1);Build(1, 1, n);char opt[13];while(m--){int l, r;scanf("%s", opt + 1);io >> l >> r;if(opt[1] == 'C'){int newColor;io >> newColor;PathUpdata(l, r, newColor);}else{printf("%d\n", PathQuery(l, r));}}//  TIME();return 0;
}

「SDOI2014」旅行

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))//#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
//#define TIME() Debug("\nTime: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 100007;int n;struct Edge{int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge){ head[u], v}, head[u] = cntEdge;
}int val[N], faith[N];
int siz[N], son[N], fa[N], dep[N];
inline void DFS_First(int u, int father){dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;DFS_First(v, u);siz[u] += siz[v];if(!son[u] || siz[v] > siz[son[u]])son[u] = v;}
}
int dfn[N], dfnIndex, top[N];
inline void DFS_Second(int u, int TP){dfn[u] = ++dfnIndex, top[u] = TP;if(!son[u]) return;DFS_Second(son[u], TP);for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v != fa[u] && v != son[u])DFS_Second(v, v);}
}#define lson t[rt].l, l, mid
#define rson t[rt].r, mid + 1, r
#define ls t[rt].l
#define rs t[rt].r
struct Tree{long long sum;int l, r, mx;
}t[N * 300];
int treeIndex, T[N];
inline void Pushup(int &rt){t[rt].sum = t[ls].sum + t[rs].sum;
//  D_e(t[dfn[3]].sum);
//  D_e(rt);t[rt].mx = max(t[ls].mx, t[rs].mx);
}
inline void Change(int &rt, int l, int r, int &x, int w){ // !if(!rt){rt = ++treeIndex;t[rt].sum = t[rt].mx = t[rt].l = t[rt].r = 0;}if(l == r){t[rt].sum = t[rt].mx = w;return;}int mid = (l + r) >> 1;if(mid >= x)Change(lson, x, w);elseChange(rson, x, w);Pushup(rt);
}
inline int QueryMax(int rt, int l, int r, int L, int R){if(L <= l && r <= R) return t[rt].mx;if(!rt) return 0;int mid = (l + r) >> 1, maxx = -0x7fffffff;if(mid >= L) maxx = max(maxx, QueryMax(lson, L, R));if(mid < R) maxx = max(maxx, QueryMax(rson, L, R));return maxx;
}
inline long long QuerySum(int rt, int l, int r, int L, int R){if(L <= l && r <= R) return t[rt].sum;if(!rt) return 0;int mid = (l + r) >> 1;long long sum = 0;if(mid >= L) sum += QuerySum(lson, L, R);if(mid < R) sum += QuerySum(rson, L, R);return sum;
}inline long long PathQuerySum(int x, int y, int &belief){long long sum = 0;//D_e(top[x]), D_e(top[y]);while(top[x] != top[y]){//D_e_Line;if(dep[top[x]] < dep[top[y]]) Swap(x, y);sum += QuerySum(T[belief], 1, n, dfn[top[x]], dfn[x]);x = fa[top[x]];}if(dep[x] < dep[y]) Swap(x, y); // ! OH, shitttttttttttttttttttttttreturn sum + QuerySum(T[belief], 1, n, dfn[y], dfn[x]);
}
inline int PathQueryMax(int x, int y, int &belief){int maxx = -0x7fffffff;while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) Swap(x, y);maxx = max(maxx, QueryMax(T[belief], 1, n, dfn[top[x]], dfn[x]));x = fa[top[x]];}if(dep[x] < dep[y]) Swap(x, y);return max(maxx, QueryMax(T[belief], 1, n, dfn[y], dfn[x]));
}int main(){
//FileOpen();int m;io >> n >> m;R(i,1,n){io >> val[i] >> faith[i];}R(i,2,n){int u, v;io >> u >> v;add(u, v);add(v, u);}DFS_First(1, 0);DFS_Second(1, 1);R(i,1,n) Change(T[faith[i]], 1, n, dfn[i], val[i]);
//  R(i,1,n){
//      D_e(t[dfn[i]].sum);
//  }while(m--){char opt[13];int x, y;scanf("%s", opt + 1);io >> x >> y;if(opt[2] == 'S'){printf("%lld\n", PathQuerySum(x, y, faith[y]));}else if(opt[2] == 'C'){Change(T[faith[x]], 1, n, dfn[x], 0);faith[x] = y; // !Change(T[faith[x]], 1, n, dfn[x], val[x]); // !}else if(opt[2] == 'W'){Change(T[faith[x]], 1, n, dfn[x], y);val[x] = y;}else{printf("%d\n", PathQueryMax(x, y, faith[y]));}}
//  TIME();return 0;
}

线段树

最大数

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;#endif
using namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 200007;
const int M = 200000;int n;#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
int t[N << 2];
inline void Pushup(int rt){t[rt] = max(t[rt << 1], t[rt << 1 | 1]);
}
inline void Updata(int rt, int l, int r, int L, int R, long long w){if(L <= l && r <= R){t[rt] += w;return;}int mid = (l + r) >> 1;if(mid >= L) Updata(lson, L, R, w);if(mid < R) Updata(rson, L, R, w);Pushup(rt);
}
inline long long Query(int rt, int l, int r, int L, int &R){if(L <= l && r <= R) return t[rt];int mid = (l + r) >> 1;long long maxx = -0x7fffffff;if(mid >= L) maxx = max(maxx, Query(lson, L, R));if(mid < R) maxx = max(maxx, Query(rson, L, R));return maxx;
}int main(){int mod, m;long long lastAns = 0;io >> m >> mod;while(m--){char opt[13];scanf("%s", opt + 1);if(opt[1] == 'A'){int x;io >> x;++n;Updata(1, 1, N, n, n, (x % mod + lastAns) % mod);}else{int L;io >> L;lastAns = Query(1, 1, N, n - L + 1, n);printf("%lld\n", lastAns);}}return 0;
} 

维护序列

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;#endif
using namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 100007;int n;
int mod;#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
long long t[N << 2], add[N << 2], mul[N << 2];
inline void Pushup(int &rt){t[rt] = (t[rt << 1] + t[rt << 1 | 1]) % mod;
}
inline void Pushdown(int &rt, int &l, int &r){int mid = (l + r) >> 1;t[rt << 1] = (t[rt << 1] * mul[rt] + add[rt] * (mid - l + 1) % mod) % mod;t[rt << 1 | 1] = (t[rt << 1 | 1] * mul[rt] + add[rt] * (r - mid) % mod) % mod;mul[rt << 1] = (mul[rt << 1] * mul[rt]) % mod;mul[rt << 1 | 1] = (mul[rt << 1 | 1] * mul[rt]) % mod;add[rt << 1] = (add[rt << 1] * mul[rt] + add[rt]) % mod;add[rt << 1 | 1] = (add[rt << 1 | 1] * mul[rt] + add[rt]) % mod;mul[rt] = 1, add[rt] = 0;
}
inline void Build(int rt, int l, int r){mul[rt] = 1;if(l == r){io >> t[rt];return;}int mid = (l + r) >> 1;Build(lson), Build(rson);Pushup(rt);
}
inline void UpdataAdd(int rt, int l, int r, int L, int R, int w){if(L <= l && r <= R){t[rt] = (t[rt] + (r - l + 1) * w % mod) % mod;add[rt] = (add[rt] + w) % mod;return;}if(add[rt] || mul[rt] != 1) Pushdown(rt, l, r);int mid = (l + r) >> 1;if(L <= mid) UpdataAdd(lson, L, R, w);if(R > mid) UpdataAdd(rson, L, R, w);Pushup(rt);
}
inline void UpdataMul(int rt, int l, int r, int L, int R, int w){if(L <= l && r <= R){t[rt] = t[rt] * w % mod;add[rt] = add[rt] * w % mod;mul[rt] = mul[rt] * w % mod;return;}if(add[rt] || mul[rt] != 1) Pushdown(rt, l, r);int mid = (l + r) >> 1;if(L <= mid) UpdataMul(lson, L, R, w);if(R > mid) UpdataMul(rson, L, R, w);Pushup(rt);
}
inline long long Query(int rt, int l, int r, int L, int R){if(L <= l && r <= R) return t[rt];if(add[rt] || mul[rt] != 1) Pushdown(rt, l, r);int mid = (l + r) >> 1;long long sum = 0;if(L <= mid) sum = (sum + Query(lson, L, R)) % mod;if(R > mid) sum = (sum + Query(rson, L, R)) % mod;return sum;
}int main(){
FileOpen();int m;io >> n >> mod;Build(1, 1, n);io >> m;while(m--){int opt;io >> opt;if(opt == 1){int l, r, w;io >> l >> r >> w;UpdataMul(1, 1, n, l, r, w);}else if(opt == 2){int l, r, w;io >> l >> r >> w;UpdataAdd(1, 1, n, l, r, w);            }else{int l, r;io >> l >> r;printf("%lld\n", (Query(1, 1, n, l, r) + mod) % mod);}}return 0;
}

树状数组

校门外的树

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
//#define TIME() Debug("\nTime: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 50007;int n;int L[N], R[N];
inline void Updata(int *t, int x){for(; x <= n; x += x & -x) ++t[x];
}
inline int Query(int *t, int x){int sum = 0;for(; x; x -= x & -x) sum += t[x];return sum;
}int main(){int m;io >> n >> m;while(m--){int opt, l, r;io >> opt >> l >> r;if(opt == 1){Updata(L, l);Updata(R, r);}else{printf("%d\n", Query(L, r) - Query(R, l - 1));}}return 0;
}

简单题

线段树打错了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
//#define TIME() Debug("\nTime: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 100007;int t[N], n;
inline void Updata(int x){for(; x <= n; x += x & -x) t[x] ^= 1;
}
inline int Query(int x){int sum = 0;for(; x; x -= x & -x) sum ^= t[x];return sum;
}
int main(){
//FileOpen();int m;io >> n >> m;while(m--){int opt;io >> opt;if(opt == 1){int l, r;io >> l >> r;Updata(l);Updata(r + 1);}else{int x;io >> x;printf("%d\n", Query(x));}}return 0;
}
/*
#include "Head.cpp"const int N = 100007;int n;
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1
int t[N << 2], tag[N << 2];
inline void Pushup(int &rt){t[rt] = t[ls] + t[rs];
}
inline void Pushdown(int &rt, int l, int r, int mid){tag[ls] ^= 1;tag[rs] ^= 1;t[ls] =  -t[ls] + mid - l + 1;t[rs] = -t[rs] + r - mid;tag[rt] = 0;
}
inline void Updata(int rt, int l, int r, int L, int R){if(L <= l && r <= R){t[rt] = -t[rt] + r - l + 1;tag[rt] ^= 1;return;}int mid = (l + r) >> 1;if(tag[rt]) Pushdown(rt, l, r, mid);if(L <= mid) Updata(lson, L, R);if(R > mid) Updata(rson, L, R);Pushup(rt);
}
inline int Query(int rt, int l, int r, int L, int R){if(L <= l && r <= R) return t[rt];int mid = (l + r) >> 1;if(tag[rt]) Pushdown(rt, l, r, mid);int sum = 0;if(L <= mid) sum += Query(lson, L, R);if(R > mid) sum += Query(rson, L, R);Pushup(rt);
}
int main(){
FileOpen();int m;io >> n >> m;while(m--){int opt;io >> opt;if(opt == 1){int l, r;io >> l >> r;Updata(1, 1, n, l, r);}else{int x;io >> x;printf("%d\n", Query(1, 1, n, x, x) - Query(1, 1, n, x - 1, x - 1));}}return 0;
}
*/

单点修改，区间查询 1

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
//#define TIME() Debug("\nTime: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 1000007;#define int long long
int n, t[N];
inline void Updata(int x, int w){for(; x <= n; x += x & -x) t[x] += w;
}
inline int Query(int x){int sum = 0;for(; x; x -= x & -x) sum += t[x];return sum;
}
#undef int
int main(){
#define int long long
//FileOpen();
//FileSave();int m;io >> n >> m;++n;R(i,2,n){int w;io >> w;Updata(i, w);}while(m--){int opt;io >> opt;if(opt == 1){int x, w;io >> x >> w;++x;Updata(x, w);//Updata(x - 1, -w);}else{int l, r;io >> l >> r;++l, ++r;printf("%lld\n", Query(r) - Query(l - 1));}}return 0;
}

区间修改，单点查询

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))//#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
//#define TIME() Debug("\nTime: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 1000007;#define int long long
int n, t[N];
inline void Updata(int x, int w){for(; x <= n; x += x & -x) t[x] += w;
}
inline int Query(int x){int sum = 0;for(; x; x -= x & -x) sum += t[x];return sum;
}#undef int
int main(){
#define int long long
//FileOpen();
//FileSave();int m;io >> n >> m;int last = 0;R(i,1,n){int w;io >> w;Updata(i, w - last);last = w;}while(m--){int opt;io >> opt;if(opt == 1){int l, r, w;io >> l >> r >> w;Updata(l, w);Updata(r + 1, -w);//Updata(x - 1, -w);}else{int x;io >> x;printf("%lld\n", Query(x));}}return 0;
}

二维树状数组 1：单点修改，区间查询

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
//#define TIME() Debug("\nTime: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}const int N = 4507;
#define int long long
int n, m;int t[N][N];
inline void Updata(int x, int y, int w){for(; x <= n; x += x & -x)for(register int i = y; i <= m; i += i & -i)t[x][i] += w;
}
inline int Query(int x, int y){int sum = 0;for(; x; x -= x & -x)for(register int i = y; i; i -= i & -i)sum += t[x][i];//D_e(sum);return sum;
}
#undef int
int main(){
#define int long longio >> n >> m;int opt;++n, ++m;while(~scanf("%lld", &opt)){if(opt == 1){int x, y, w;io >> x >> y >> w;++x, ++y;Updata(x, y, w);}else{int a, b, c, d;io >> a >> b >> c >> d;
//          a,b   c,b
//          a,d   c,d++a, ++b, ++c, ++d;printf("%lld\n", -Query(a - 1, d) - Query(c, b - 1) + Query(a - 1, b - 1) + Query(c, d));}}return 0;
}

平衡树

营业额统计

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 65547;#define ls(rt) t[rt].ch[0]
#define rs(rt) t[rt].ch[1]
#define fa(rt) t[rt].fa
struct Tree{int ch[2], fa, val, tot, siz;
}t[N];
int treeIndex, root;
inline void Pushup(int rt){t[rt].siz = t[t[rt].ch[0]].siz + t[t[rt].ch[1]].siz + t[rt].tot;
}
inline int Ident(int rt){return rt == t[t[rt].fa].ch[1];
}
inline void Rotate(int x){int y = t[x].fa, z = t[y].fa, k = Ident(x);t[z].ch[Ident(y)] = x, t[x].fa = z;t[y].ch[k] = t[x].ch[k ^ 1], t[t[x].ch[k ^ 1]].fa = y;t[x].ch[k ^ 1] = y, t[y].fa = x;Pushup(y), Pushup(x);
}
inline void Splay(int x, int pos){while(t[x].fa != pos){int y = t[x].fa, z = t[y].fa;if(z != pos){Ident(x) == Ident(y) ? Rotate(y) : Rotate(x);}Rotate(x);}if(!pos) root = x;
}
inline void Find(int x){int u = root;if(!u) return;while(t[u].ch[x > t[u].val] && t[u].val != x) u = t[u].ch[x > t[u].val];Splay(u, 0);
}
inline void Insert(int x){int u = root, fa = 0;while(u && t[u].val != x){fa = u;u = t[u].ch[x > t[u].val];}if(u){++t[u].tot;}else{u = ++treeIndex;t[u].fa = fa;t[u].val = x;t[u].siz = t[u].tot = 1;t[u].ch[0] = t[u].ch[1] = 0;if(fa) t[fa].ch[x > t[fa].val] = u;}Splay(u, 0);
}
inline int Next(int x, int type){Find(x);int u = root;if(t[u].val >= x && type) return u;if(t[u].val <= x && !type) return u;u = t[u].ch[type];while(t[u].ch[type ^ 1]) u = t[u].ch[type ^ 1];return u;
}int main(){int n;io >> n;Insert(1e9);Insert(-1e9);int ans;io >> ans;Insert(ans);//D_e(ans);R(i,2,n){int x;io >> x;ans += min(abs(t[Next(x, 0)].val - x), abs(t[Next(x, 1)].val - x));Insert(x);}printf("%d", ans);return 0;
}

宠物收养所

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma -fcrossjumping
#pragma -fdefer-pop
#pragma -fmerge-constans
#pragma -fthread-jumps
#pragma -floop-optimize
#pragma -fif-conversion
#pragma -fif-conversion2
#pragma -fdelayed-branch
#pragma -fguess-branch-probability
#pragma -fcprop-registers
#pragma -fforce-mem
#pragma -foptimize-sibling-calls
#pragma -fstrength-reduce
#pragma -fgcse
#pragma -fcse-follow-jumps
#pragma -frerun-cse-after-loop
#pragma -fdelete-null-pointer-checks
#pragma -fextensive-optimizations
#pragma -fregmove
#pragma -fschedule-insns
#pragma -fsched-interblock
#pragma -fcaller-saves
#pragma -fpeephole2
#pragma -freorder-blocks
#pragma -fstrict-aliasing
#pragma -funit-at-a-time
#pragma -falign-functions
#pragma -fcrossjumping
#pragma -finline-functions
#pragma -fweb
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}#define int long long 
const int mod = 1000000;
const int N = 100007;struct Tree{int ch[2], fa, val, siz;
}t[N];
int treeIndex, root;
inline void Pushup(int &rt){t[rt].siz = t[t[rt].ch[0]].siz + t[t[rt].ch[1]].siz + 1;
}
inline int Ident(int &rt){return rt == t[t[rt].fa].ch[1];
}
inline void Rotate(int x){int y = t[x].fa, z = t[y].fa, k = Ident(x);t[z].ch[Ident(y)] = x, t[x].fa = z,t[y].ch[k] = t[x].ch[k ^ 1], t[t[x].ch[k ^ 1]].fa = y,t[x].ch[k ^ 1] = y, t[y].fa = x,Pushup(y), Pushup(x);
}
inline void Splay(int x, int pos){while(t[x].fa != pos){int y = t[x].fa, z = t[y].fa;   if(z != pos){ Ident(x) == Ident(y) ? Rotate(y) : Rotate(x); }Rotate(x);}if(!pos) root = x; 
}
inline void Find(int x){int u = root;if(!u) return;while(t[u].ch[x > t[u].val] && t[u].val != x) u = t[u].ch[x > t[u].val];Splay(u, 0);
}
inline void Insert(int x){int u = root, fa = 0;while(u && t[u].val != x){fa = u,u = t[u].ch[x > t[u].val];}u = ++treeIndex,t[u].val = x,t[u].siz = 1,t[u].fa = fa,t[u].ch[0] = t[u].ch[1] = 0;if(fa) t[fa].ch[x > t[fa].val] = u;Splay(u, 0);
}
inline int Next(int x, int type){Find(x);int u = root;if(t[u].val < x && !type) return u;if(t[u].val > x && type) return u;/*if write <= or >=, it may RE in Splay()*/u = t[u].ch[type];while(t[u].ch[type ^ 1]) u = t[u].ch[type ^ 1];return u;
}
inline void Delete(int x){int pre = Next(x, 0), nxt = Next(x, 1);Splay(pre, 0), Splay(nxt, pre);t[nxt].ch[0] = 0;
}#undef int
int main(){
#define int long long
//FileOpen();int n;io >> n;int store = 0, ans = 0, opt, x;Insert(2147483647);Insert(-2147483647);R(i,1,n){io >> opt >> x;if(store == 0) Insert(x);else if(store > 0){ // petif(opt == 0){Insert(x);}else{int pre = Next(x, 1), nxt = Next(x, 0);if(abs(t[nxt].val - x) <= abs(t[pre].val - x)){ans = (ans + abs(t[nxt].val - x)) % mod,Delete(t[nxt].val);}else{ans = (ans + abs(t[pre].val - x)) % mod,Delete(t[pre].val);}}}else{ // peopleif(opt == 1){Insert(x);}else{int pre = Next(x, 1), nxt = Next(x, 0);if(abs(t[nxt].val - x) <= abs(t[pre].val - x)){ans = (ans + abs(t[nxt].val - x)) % mod,Delete(t[nxt].val);}else{ans = (ans + abs(t[pre].val - x)) % mod,Delete(t[pre].val);}}}store += (opt == 0 ? 1 : -1);}printf("%lld", ans);return 0;
}
/*
5
0 2
0 4
1 3
1 2
1 5
*/

郁闷的出纳员

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long//#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 100007;int minLimit, totLeave;
struct Treap{int ch[2], fa, val, tot, siz;
}t[N];
int root, treeIndex;
inline void Pushup(int &rt){t[rt].siz = t[t[rt].ch[0]].siz + t[t[rt].ch[1]].siz + t[rt].tot;
}
inline int Ident(int &rt){return rt == t[t[rt].fa].ch[1];
} 
inline void Rotate(int x){int y = t[x].fa, z = t[y].fa, k = Ident(x);t[z].ch[Ident(y)] = x, t[x].fa = z;t[y].ch[k] = t[x].ch[k ^ 1], t[t[x].ch[k ^ 1]].fa = y;t[x].ch[k ^ 1] = y, t[y].fa = x;Pushup(y), Pushup(x);
}
inline void Splay(int x, int pos){while(t[x].fa != pos){int y = t[x].fa, z = t[y].fa;if(z != pos){Ident(x) == Ident(y) ? Rotate(y) : Rotate(x);}Rotate(x);}if(!pos) root = x; //!!!!
}
inline void Find(int x){int u = root;if(!u) return;while(t[u].val != x && t[u].ch[x > t[u].val]) u = t[u].ch[x > t[u].val];Splay(u, 0);
}
inline void Insert(int x){if(x < minLimit) return;int u = root, fa = 0;while(u && t[u].val != x){fa = u;u = t[u].ch[x > t[u].val];}if(u){++t[u].tot;}else{u = ++treeIndex;t[u].val = x;t[u].siz = t[u].tot = 1;t[u].ch[0] = t[u].ch[1] = 0;t[u].fa = fa;if(fa) t[fa].ch[x > t[fa].val] = u; //!!}Splay(u, 0);
} 
inline void Add(int w){R(i,1,treeIndex) t[i].val += w;
}
inline void Sub(int w){R(i,1,treeIndex) t[i].val -= w;
}
inline int Next(int x){Find(x);int u = root;if(t[u].val >= x) return u;u = t[u].ch[1];while(t[u].ch[0]) u = t[u].ch[0];return u;
}
inline void Remove(int x){int rt = Next(x + minLimit);Splay(rt, 0);totLeave += t[t[rt].ch[0]].siz;t[rt].ch[0] = 0;Pushup(rt);Sub(x);
}
inline int Kth(int x){int u = root;if(t[u].siz < x) return -1;while(1){int v = t[u].ch[1];if(t[v].siz + t[u].tot < x){x -= t[v].siz + t[u].tot;u = t[u].ch[0];}else if(x <= t[v].siz){u = v;}elsereturn t[u].val;}
}int main(){
FileOpen();
FileSave();int m;io >> m >> minLimit;Insert(2147483647);Insert(-2147483647);while(m --){char opt = getchar();while(opt != 'I' && opt != 'S' && opt != 'A' && opt != 'F') opt = getchar();int x;io >> x;if(opt == 'I'){Insert(x);}else if(opt == 'A'){Add(x);}else if(opt == 'S'){Remove(x);}else{printf("%d\n", Kth(x + 1));}}printf("%d", totLeave);return 0;
}

普通平衡树

FHQ Treap

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}#include <ctime>const int N = 100007;struct FHQ{int ch[2], val, siz, rnd, tot;
}t[N];
int root, treeIndex;
inline void Pushup(int &rt){t[rt].siz = t[t[rt].ch[0]].siz + t[t[rt].ch[1]].siz + t[rt].tot;
}
inline int NewNode(int x){++treeIndex;t[treeIndex].siz = t[treeIndex].tot = 1;t[treeIndex].val = x;t[treeIndex].rnd = rand();return treeIndex;
}
inline int Merge(int x, int y){if(!x || !y) return x | y;if(t[x].rnd < t[y].rnd){t[x].ch[1] = Merge(t[x].ch[1], y);Pushup(x);return x;}else{t[y].ch[0] = Merge(x, t[y].ch[0]);Pushup(y);return y;}
}
inline void Split(int u, int w, int &x, int &y){if(!u)x = y = 0;else{if(t[u].val <= w){x = u;Split(t[u].ch[1], w, t[u].ch[1], y);}else{y = u;Split(t[u].ch[0], w, x, t[u].ch[0]);}Pushup(u);}
}
inline int Kth(int u, int K){while(1){int v = t[u].ch[0];if(t[v].siz + t[u].tot < K){K -= t[v].siz + t[u].tot;u = t[u].ch[1];}else if(K <= t[v].siz){u = v;}elsereturn u;}
}int main(){
//FileOpen();srand((unsigned)time(NULL));int m;io >> m;int root = 0, x, y, z;int opt, a;while(m--){io >> opt >> a;if(opt == 1){Split(root, a, x, y);;root = Merge(Merge(x, NewNode(a)), y);}else if(opt == 2){Split(root, a, x, z);Split(x, a - 1, x, y);y = Merge(t[y].ch[0], t[y].ch[1]);root = Merge(Merge(x, y), z);}else if(opt == 3){Split(root, a - 1, x, y);printf("%d\n", t[x].siz + 1);root = Merge(x, y);}else if(opt == 4){printf("%d\n", t[Kth(root, a)].val);} else if(opt == 5){Split(root, a - 1, x, y);printf("%d\n", t[Kth(x, t[x].siz)].val);root = Merge(x, y);}else{Split(root, a, x, y);printf("%d\n", t[Kth(y, 1)].val);root = Merge(x, y);}}return 0;
}

Splay

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long//#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 100007;int minLimit, totLeave;
struct Treap{int ch[2], fa, val, tot, siz;
}t[N];
int root, treeIndex;
inline void Pushup(int &rt){t[rt].siz = t[t[rt].ch[0]].siz + t[t[rt].ch[1]].siz + t[rt].tot;
}
inline int Ident(int &rt){return rt == t[t[rt].fa].ch[1];
} 
inline void Rotate(int x){int y = t[x].fa, z = t[y].fa, k = Ident(x);t[z].ch[Ident(y)] = x, t[x].fa = z;t[y].ch[k] = t[x].ch[k ^ 1], t[t[x].ch[k ^ 1]].fa = y;t[x].ch[k ^ 1] = y, t[y].fa = x;Pushup(y), Pushup(x);
}
inline void Splay(int x, int pos){while(t[x].fa != pos){int y = t[x].fa, z = t[y].fa;if(z != pos){Ident(x) == Ident(y) ? Rotate(y) : Rotate(x);}Rotate(x);}if(!pos) root = x; //!!!!
}
inline void Find(int x){int u = root;if(!u) return;while(t[u].val != x && t[u].ch[x > t[u].val]) u = t[u].ch[x > t[u].val];Splay(u, 0);
}
inline void Insert(int x){if(x < minLimit) return;int u = root, fa = 0;while(u && t[u].val != x){fa = u;u = t[u].ch[x > t[u].val];}if(u){++t[u].tot;}else{u = ++treeIndex;t[u].val = x;t[u].siz = t[u].tot = 1;t[u].ch[0] = t[u].ch[1] = 0;t[u].fa = fa;if(fa) t[fa].ch[x > t[fa].val] = u; //!!}Splay(u, 0);
} 
inline void Add(int w){R(i,1,treeIndex) t[i].val += w;
}
inline void Sub(int w){R(i,1,treeIndex) t[i].val -= w;
}
inline int Next(int x){Find(x);int u = root;if(t[u].val >= x) return u;u = t[u].ch[1];while(t[u].ch[0]) u = t[u].ch[0];return u;
}
inline void Remove(int x){int rt = Next(x + minLimit);Splay(rt, 0);totLeave += t[t[rt].ch[0]].siz;t[rt].ch[0] = 0;Pushup(rt);Sub(x);
}
inline int Kth(int x){int u = root;if(t[u].siz < x) return -1;while(1){int v = t[u].ch[1];if(t[v].siz + t[u].tot < x){x -= t[v].siz + t[u].tot;u = t[u].ch[0];}else if(x <= t[v].siz){u = v;}elsereturn t[u].val;}
}int main(){
FileOpen();
FileSave();int m;io >> m >> minLimit;Insert(2147483647);Insert(-2147483647);while(m --){char opt = getchar();while(opt != 'I' && opt != 'S' && opt != 'A' && opt != 'F') opt = getchar();int x;io >> x;if(opt == 'I'){Insert(x);}else if(opt == 'A'){Add(x);}else if(opt == 'S'){Remove(x);}else{printf("%d\n", Kth(x + 1));}}printf("%d", totLeave);return 0;
}

暗的连锁

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 100007;int n;struct Edge{int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge){ head[u], v}, head[u] = cntEdge;
}int top[N], dep[N], fa[N], son[N], siz[N]; 
inline void DFS_First(int u, int father){dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;DFS_First(v, u);siz[u] += siz[v];if(!son[u] || siz[v] > siz[son[u]]) son[u] = v;}
}
inline void DFS_Second(int u, int TP){top[u] = TP;if(!son[u]) return;DFS_Second(son[u], TP);for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v != fa[u] && v != son[u])DFS_Second(v, v);}
}
inline int LCA(int x, int y){while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]]) Swap(x, y);x = fa[top[x]];}return dep[x] < dep[y] ? x : y;
}long long ans;
int sum[N], m;
inline void DFS_Ans(int u){for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == fa[u]) continue;DFS_Ans(v);sum[u] += sum[v];if(sum[v] == 0){ans += m;}else if(sum[v] == 1){++ans;}/*Since the edge weight is delegated to the point weight, thecontribution of u to the answer can not be counted directlyin the back. Otherwise, the root will affect the result.*/}
}
int main(){
//FileOpen();io >> n >> m;R(i,2,n){int u, v;io >> u >> v;add(u, v);add(v, u);}   DFS_First(1, 0);DFS_Second(1, 1);R(i,1,m){int u, v;io >> u >> v;++sum[u], ++sum[v];sum[LCA(u, v)] -=2;}DFS_Ans(1);printf("%lld", ans);return 0;
}

区间DP

凸多边形的划分

莫名RE ing...

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;int n, a[107];
struct BIGN {const static int LEN = 10, base = 1000000000;int a[11];BIGN(int b = 0) {Fill(a, 0);a[LEN] = b;//R(i,0,10) if(a[i]) D_e(a[i]);}void InitMax(){R(i,1,LEN) a[i] = INT_MAX;}BIGN operator + (const BIGN &b){BIGN s;int c = 0;nR(i,LEN,1){s.a[i] = b.a[i] + a[i] + c;c = s.a[i] / base;s.a[i] %= base;}return s;}BIGN operator * (int b){BIGN s;int c = 0;nR(i,LEN,1){long long t = a[i] * b + c;s.a[i] = t % base;c = t / base;}return s;}bool operator < (const BIGN &b) const {R(i,1,LEN){if(a[i] != b.a[i])return a[i] < b.a[i];} return 0;}void print(){int flag = 0;R(i,1,LEN){//D_e(a[i]);if(flag){printf("%09d", a[i]);}else if(a[i]){printf("%d", a[i]);flag = 1;}}}}f[107][107], ans;int main(){
//FileOpen();int n;io >> n;R(i,1,n){io >> a[i];a[n + i] = a[i];}int m = n << 1;R(len,2,n){R(l,1,m){int r = l + len;f[l][r].InitMax();R(k,l + 1,r - 1){BIGN tmp = f[l][k] + f[k][r] + (1ll * a[l] * a[k] * a[r]);f[l][r] = min(f[l][r], tmp);}}}R(i,1,n){ans = max(ans, f[i][i + n - 1]);}ans.print();return 0;
}

树形DP

二叉苹果树

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 107;struct Edge{int nxt, pre, w;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v, int w){e[++cntEdge] = (Edge){ head[u], v, w}, head[u] = cntEdge;
}int n, m;
int siz[N], f[N][N];
inline void DFS(int u, int father){siz[u] = 1;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;DFS(v, u);siz[u] += siz[v];nR(j,min(siz[u], m),1){nR(k,min(m,j),1){f[u][j] = max(f[u][j], f[u][j - k] + f[v][k - 1] + e[i].w);}}}}int main(){io >> n >>m;R(i,2,n){int u, v, w;io >> u >> v >> w;add(u, v, w);add(v, u, w);}DFS(1, 0);int ans = 0;R(i,0,m) ans = max(ans, f[1][i]);printf("%d", ans);return 0;
}

选课

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;#endifusing namespace std;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 1007;struct Edge{int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge){head[u], v}, head[u] = cntEdge;
}
int n, m;int f[N][N], siz[N];
inline void DFS(int u){siz[u] = 1;for(register int i = head[u]; i; i = e[i].nxt){int v= e[i].pre;DFS(v);siz[u] += siz[v];nR(j,min(siz[u] - 1, m),0){int maxn = min(j - 1, siz[v] - 1);R(k,0,maxn){f[u][j] = max(f[u][j], f[u][j - k - 1] + f[v][k]);}}}
}
int main(){
//FileOpen();io >> n >> m;
//  ++m;R(i,1,n){int fa;io >> fa >> f[i][0];add(fa, i);}DFS(0);printf("%d",f[0][m]);return 0;
}

战略游戏

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 1507;struct Edge{int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge){ head[u], v}, head[u] = cntEdge;
}int f[N][N];
inline void DFS(int u, int father){f[u][1] = 1;for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;DFS(v, u);f[u][0] += f[v][1];f[u][1] += min(f[v][1], f[v][0]);}
}
int main(){int n;io >> n;R(i,1,n){int u, K, v;io >> u >> K;++u;R(i,1,K){io >> v;++v;add(u, v);add(v, u);}}DFS(1, 0);printf("%d", min(f[1][0], f[1][1]));return 0;
}

数字转换

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 50007;struct Edge{int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){e[++cntEdge] = (Edge){head[u], v}, head[u] = cntEdge;
}int n;namespace DP{
int d[N], maxDis;
inline void DFS(int u, int father){for(register int i = head[u]; i; i = e[i].nxt){int v = e[i].pre;if(v == father) continue;DFS(v, u);maxDis = max(maxDis, d[u] + d[v] + 1);d[u] = max(d[u], d[v] + 1);}
}}namespace PRIME{int prime[N], vis[N], tot;
inline void EularSieve(){R(i,2,n){if(!vis[i]) prime[++tot] = i;for(register int j = 1; j <= tot; ++j){if(i * prime[j] > n) break;vis[i * prime[j]] = 1;}}
}
inline int Calc(int x){if(!vis[x]) return 1;int sum = 1;int m = sqrt(x);register int i;for(i = 2; i <= m; ++i){if(x % i == 0){if(i * i == x)sum += i;elsesum += i + x / i;}}
//  for(i = 2; i <= m; ++i){
//      if(x % i == 0){
//          sum += i + x / i;
//      }
//  }
//  if(i * i == x) sum -= i;return sum;
}
}
int main(){
//FileOpen();io >> n;PRIME::EularSieve();R(i,1,n){int num = PRIME::Calc(i);if(num < i){add(num, i);add(i, num);}}DP::DFS(1, 0);printf("%d", DP::maxDis);//TIME();return 0;
}

加分二叉树

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 37;int c[N][N], f[N][N];
inline void PrintPath(int l, int r){if(l > r) return;if(l == r){printf("%d ", l);return;}printf("%d ", c[l][r]);PrintPath(l, c[l][r] - 1),PrintPath(c[l][r] + 1, r);
}int main(){int n;io >> n;R(i,1,n){io >> f[i][i];f[i][i - 1] = 1;}nR(l,n - 1,1){R(r,l + 1,n){R(k,l,r){if(f[l][r] < f[l][k - 1] * f[k + 1][r] + f[k][k]){f[l][r] = f[l][k - 1] * f[k + 1][r] + f[k][k];c[l][r] = k;}}}}printf("%d\n", f[1][n]);PrintPath(1, n);return 0;
}

状压DP

国王

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 11;int sum[2049], a[2049];
long long f[11][2049][101];
int main(){int n, m;io >> n >> m;int maxn = 1 << n;int tot = 0;for(register int s = 0; s < maxn; ++s){if((s & (s >> 1)) || (s & (s << 1))) continue;a[++tot] = s;int x = s;while(x){sum[tot] += x & 1;x >>= 1;}}R(s,1,tot){f[1][s][sum[s]] = 1;}R(i,2,n){R(j,1,tot){R(k,1,tot){if((a[k] & a[j]) || (a[k] & (a[j] << 1)) || (a[k] & (a[j] >> 1))) continue;R(l,sum[j] + sum[k],m){f[i][j][l] += f[i - 1][k][l - sum[j]];}}}}long long ans = 0;R(i,1,tot){ans += f[n][i][m];}printf("%lld", ans);return 0;
}

牧场的安排

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 13;
const int mod = 100000000;int tot[N], a[N][(1 << 12) + 7];
long long f[N][(1 << 12) + 7];
int main(){
//FileOpen();int n, m;io >> n >> m;int maxn = (1 << m) - 1;R(i,1,n){int x, t = 0;R(j,1,m){io >> x;t = (t << 1) - x + 1;}R(j,0,maxn){if((j &(j << 1)) || (j & (j >> 1)) || (j & t)) continue;a[i][++tot[i]] = j;}}R(i,1,tot[1]) f[1][i] = 1;R(i,1,n){R(j,1,tot[i]){R(k,1,tot[i - 1]){if(a[i][j] & a[i - 1][k]) continue;f[i][j] = (f[i][j] + f[i - 1][k]) % mod;}}}long long ans = 0;R(i,1,tot[n]){ans = (ans + f[n][i]) % mod;}printf("%lld", ans);return 0;
}

涂抹果酱

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int mod = 1000000;int n, m, K;
long long f[10007][247];
inline int Pow(int a, int b){int s = 1;a %= mod;while(b){if(b & 1) s = s * a % mod;a = a  * a % mod, b >>= 1;}return s;
}
inline bool Judge(int x){int tmp = x % 3;x /= 3;R(i,2,m){if(tmp == x % 3) return false;tmp = x % 3, x /= 3;}return true;
}
inline bool Check(int x, int y){R(i,1,m){if(x % 3 == y % 3) return false;x /= 3, y /= 3;}return true;
}
int sta[737], tot;
int main(){
//FileOpen();io >> n >> m >> K;int maxn = Pow(3, m) - 1, num = 0;R(i,1,m){int x;io >> x;num = num * 3 + x - 1;}int tot = 0, pos = 0;R(i,0,maxn){if(Judge(i)){sta[++tot] = i;if(i == num) pos = tot;} }if(!pos){printf("0");return 0;}R(i,1,n){if(i == K){if(i == 1){f[i][pos] = 1;}else{R(j,1,tot){if(Check(sta[j], sta[pos])){f[i][pos] = (f[i][pos] + f[i - 1][j]) % mod;}}}}else{if(i == 1){R(j,1,tot){f[i][j] = 1;}}else{R(j,1,tot){R(k,1,tot){if(Check(sta[j], sta[k])){f[i][j] = (f[i][j] + f[i - 1][k]) % mod;}}}}}}long long ans = 0;R(i,1,tot){ans = (ans + f[n][i]) % mod;}printf("%lld", ans);return 0;
}

动物园

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 50007;int num[N][33], f[N][33];int main(){
//FileOpen();int n, m;io >> n >> m;R(i,1,m){int E, F, L;int fear = 0, love = 0;io >> E >> F >> L;R(j,1,F){int x;io >> x;fear |= 1 << (x - E + n) % n;}R(j,1,L){int x;io >> x;love |= 1 << (x - E + n) % n;}R(j,0,31){if((j & fear) || (~j & love)){++num[E][j];}}}int ans = 0;R(s,0,31){Fill(f[0], 128);f[0][s] = 0;R(i,1,n){R(j,0,31){f[i][j] = max(f[i - 1][(j & 15) << 1], f[i - 1][(j & 15) << 1 | 1]) + num[i][j];}}ans = max(ans, f[n][s]);}printf("%d", ans);return 0;
}

单调队列优化DP

最大连续和

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 200007;struct Q{int w, id;
}q[N];
int head, tail;
int sum[N];
int main(){int n, len;io >> n >> len;int ans = -1000;R(i,1,n){int x;io >> x;sum[i] = sum[i - 1] + x;while(head <= tail && q[head].id < i - len) ++head;ans = max(ans, sum[i] - q[head].w);while(head <= tail && q[tail].w >= sum[i]) --tail;q[++tail] = (Q){sum[i], i};}printf("%d", ans);return 0;
}

修剪草坪

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 100007;struct Q{long long w;int id;
}q[N];
int head, tail;
long long f[N];
int main(){int n, len;io >> n >> len;long long sum = 0;q[++tail] = (Q){0, 0};R(i,1,n){int x;io >> x;sum += x;while(head <= tail && q[head].id < i - len) ++head;f[i] = max(f[i - 1], sum + q[head].w);while(head <= tail && q[tail].w <= f[i - 1] - sum) --tail;q[++tail] = (Q){f[i - 1] - sum, i};}printf("%lld", f[n]);return 0;
}

Banknotes

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "val", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 20007;
int w[N], val[N], a[207];
int f[200007];int main(){
//FileOpen();int n, V;io >> n;R(i,1,n) io >> a[i];int tot = 0;R(i,1,n){int num;io >> num;for(register int j = 1; j <= num; j <<= 1){w[++tot] = a[i] * j;val[tot] = j;num -= j;}if(num){w[++tot] = a[i] * num;val[tot] = num;}}io >> V;R(i,1,V) f[i] = 0x3f3f3f3f;R(i,1,tot){nR(j,V,w[i]){f[j] = min(f[j], f[j - w[i]] + val[i]);}}printf("%d", f[V]);return 0;
}

烽火传递

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 200007;
int val[N], q[N], f[N];
int main(){
//FileOpen();int n, len;io >> n >> len;R(i,1,n){io >> val[i];}int head = 0, tail = 0;R(i,1,n){while(head <= tail && i - q[head] > len) ++head;f[i] = f[q[head]] + val[i];while(head <= tail && f[q[tail]] >= f[i]) --tail;q[++tail] = i;}int ans = 0x7fffffff;R(i,n - len + 1,n){ans = min(ans, f[i]);}printf("%d", ans);return 0;
}

绿色通道

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 50007;int n, T;
int q[N], a[N], f[N];
inline bool Check(int len){int head = 0, tail = 0;R(i,1,n){while(head <= tail && i - q[head] > len) ++head;f[i] = f[q[head]] + a[i];while(head <= tail && f[q[tail]] >= f[i]) --tail;q[++tail] = i;}int ans = 0x7fffffff;R(i,n - len + 1, n){ans = min(ans, f[i]);}return ans <= T;
}int main(){io >> n >> T;R(i,1,n) io >> a[i];int l = 0, r = n, ans = 0;while(l <= r){int mid = (l + r) >> 1;if(Check(mid)){r = mid - 1;}else{ans = mid;l = mid + 1;}}printf("%d", ans);return 0;
}

[HAOI2007]理想的正方形

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 1007;int n, m, d;
int bin[23];
namespace RMQ{int fmax[N][N], fmin[N][N];
int t;inline void Init(){R(i,1,n){R(j,1,m){io >> fmax[i][j];fmin[i][j] = fmax[i][j];}}t = log2(d);R(k,0,t - 1){int maxX = n - bin[k];R(i,1,maxX){int maxY = m - bin[k];R(j,1,maxY){fmax[i][j] = max(fmax[i][j], max(fmax[i + bin[k]][j + bin[k]], max(fmax[i][j + bin[k]], fmax[i + bin[k]][j])));fmin[i][j] = min(fmin[i][j], min(fmin[i + bin[k]][j + bin[k]], min(fmin[i][j + bin[k]], fmin[i + bin[k]][j])));}}}
}
inline int Query(int x, int y){return max(fmax[x][y], max(fmax[x + d - bin[t]][y + d - bin[t]], max(fmax[x + d - bin[t]][y], fmax[x][y + d - bin[t]])))- min(fmin[x][y], min(fmin[x + d - bin[t]][y + d - bin[t]], min(fmin[x + d - bin[t]][y], fmin[x][y + d - bin[t]])));
}}int main(){
//FileOpen();io >> n >> m >> d;bin[0] = 1;R(i,1,21) bin[i] = bin[i - 1] << 1;RMQ::Init();int ans = 0x7fffffff;R(i,1,n - d + 1){R(j,1,m - d + 1){ans = min(ans, RMQ::Query(i, j));}}printf("%d\n", ans);return 0;
}

同余问题

曹冲养猪

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 17;int n;
int a[N], b[N];inline void Exgcd(ll a, ll b, ll &x, ll &y){if(!b)x = 1, y = 0;elseExgcd(b, a % b, y, x), y -= x * (a / b);
}
inline long long CRT(){long long ans = 0, M = 1;R(i,1,n) M *= a[i];R(i,1,n){ll mi = M / a[i], x, y;Exgcd(mi, a[i], x, y);x = (x % a[i] + a[i]) % a[i];ans = (ans + mi * x * b[i]) % M;}return ans < 0 ? ans + M : ans;
}
int main(){io >> n;R(i,1,n) io >> a[i] >> b[i];printf("%lld", CRT());return 0;
}

计算器

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}#include <map>#define FALSE_RESULT printf("Orz, I cannot find x!\n")int Tasks;
namespace SUBTASK1{inline long long Smul(long long a, long long b, long long &mod){return (a * b - (ll)((long double) a * b / mod) * mod + mod) % mod;
}
inline long long Pow(long long a, long long b, long long &mod){long long s = 1;while(b){if(b & 1) s = Smul(s, a, mod);a = Smul(a, a, mod), b >>= 1;}return (s + mod) % mod;
}
inline void main(){while(Tasks--){long long y, z, p;io >> y >> z >> p;printf("%lld\n", Pow(y, z, p));}
}}
namespace SUBTASK2{inline void Exgcd(ll a, ll b, ll &x, ll &y, ll &d){if(!b)x = 1, y = 0, d = a;elseExgcd(b, a % b, y, x, d), y -= x * (a / b);
}
inline void main(){while(Tasks--){long long a, b, mod, x, y, d;io >> a >> b >> mod;// a x + -mod y = bExgcd(a, mod, x, y, d);if(b % d){FALSE_RESULT;continue;}mod /= d;printf("%lld\n", (x * (b / d) % mod + mod) % mod);}
}}
namespace SUBTASK3{inline long long Smul(long long a, long long b, long long &mod){return (a * b - (ll)((long double) a * b / mod) * mod + mod) % mod;
}
inline long long Pow(long long a, long long b, long long &mod){long long s = 1;while(b){if(b & 1) s = Smul(s, a, mod);a = Smul(a, a, mod), b >>= 1;}return (s + mod) % mod;
}
map<long long, int> mp;
inline long long BSGS(long long a, long long b, long long &mod){mp.clear();int t = sqrt(mod) + 1;R(j,0,t - 1){long long val = b * Pow(a, j, mod) % mod;mp[val] = j;}a = Pow(a, t, mod);if(a == 0) return b == 0 ? 1 : -1;R(i,0,t){long long val = Pow(a, i, mod);int j = mp.find(val) == mp.end() ? -1 : mp[val];if(j >= 0 && i * t - j >= 0) return i * t - j;}return -1;
}
inline void main(){while(Tasks--){long long y, z, p;io >> y >> z >> p;if(z >= p) z %= p;long long ans = BSGS(y, z, p);if(ans == -1){FALSE_RESULT;}else{printf("%lld\n", ans);}}
}
}int main(){int opt;io >> Tasks >> opt;if(opt == 1){SUBTASK1::main();}else if(opt == 2){SUBTASK2::main();}else{SUBTASK3::main();}return 0;
}

Strange Way to Express Integers

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 100007;int n;
long long a[N], b[N];
inline long long Smul(long long a, long long b, long long &mod){return ((long long)(long double)a * b - (ll)((long double)a * b / mod) * mod + mod) % mod;
}
inline void Exgcd(ll a, ll b, ll &x, ll &y, ll &d){if(!b)x = 1, y = 0, d = a;elseExgcd(b, a % b, y, x, d), y -= x * (a / b);
}
inline long long Excrt(){long long ans = a[1], M = b[1];R(i,2,n){long long A = M, B = b[i], C = (a[i] - ans % B + B) % B, x, y, d;Exgcd(A, B, x, y, d);if(C % d) return -1;B /= d;x = Smul(x, C / d, B);ans += x * M, M *= B, ans = (ans % M + M) % M;}return ans;
}
int main(){
//FileOpen();io >> n;R(i,1,n){io >> b[i] >> a[i];}printf("%lld\n", Excrt());return 0;
}

荒岛野人

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 17;int n, maxPos;
struct node{int C, P, L;
}a[N];inline void Exgcd(int a, int b, int &x, int &y, int &d){if(!b)x = 1, y = 0, d = a;elseExgcd(b, a % b, y, x, d), y -= x * (a / b);
}
inline bool Check(int &mod){R(i,1,n){R(j,i + 1,n){int x, y, d;int A = a[i].P - a[j].P, B = mod, C = a[j].C - a[i].C;if(A < 0) A = -A, C = -C;if(C >= mod) C %= mod;Exgcd(A, B, x, y, d);if(C % d) continue; // not return! Damn it!B /= d;x = (x * (C / d) % B + B) % B;if(x <= a[i].L && x <= a[j].L) return false;}}return true;
}int main(){
//FileOpen();io >> n;R(i,1,n){io >> a[i].C >> a[i].P >> a[i].L;maxPos = max(maxPos, a[i].C);}for(register int i = maxPos; ; ++i){if(Check(i)){printf("%d", i);return 0;}}TIME();return 0;
}

组合数学

牡牛和牝牛

DP

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N  = 100007;
const int mod = 5000011;
long long f[N], g[N];
int main(){int n, K;io >> n >> K;f[1] = g[1] = 1;R(i,2,n){f[i] = f[i - 1] + g[i - 1];g[i] = (f[max(i - K - 1, 0)] + g[max(i - K - 1, 1)]) % mod;}printf("%lld", (f[n] + g[n] + mod) % mod);return 0;
}

排列组合

GuGuGu...

Combination

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); (a) <= (c); ++(a))
#define nR(a,b,c) for(register int a = (b); (a) >= (c); --(a))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ll long long
#define u32 unsigned int
#define u64 unsigned long long#define ON_DEBUGG#ifdef ON_DEBUGG#define D_e_Line printf("\n----------\n") 
#define D_e(x) cout << (#x) << " : " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#include <ctime>
#define TIME() fprintf(stderr, "\ntime: %.3fms\n", clock() * 1000.0 / CLOCKS_PER_SEC);#else#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#define FileSave() ;
#define TIME() ;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)#endifusing namespace std;
struct ios{template<typename ATP>inline ios& operator >> (ATP &x){x = 0; int f = 1; char ch;for(ch = getchar(); ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar();x *= f;return *this;}
}io;template<typename ATP>inline ATP max(ATP &a, ATP &b){return a > b ? a : b;
}
template<typename ATP>inline ATP min(ATP &a, ATP &b){return a < b ? a : b;
}
template<typename ATP>inline ATP abs(ATP &a){return a < 0 ? -a : a;
}const int N = 10013;
const int mod = 10007;int fac[N], inv[N];
inline void Init(){fac[0] = fac[1] = inv[1] =  1;R(i,2,mod) fac[i] = fac[i - 1] * i % mod;R(i,2,mod) inv[i] = (mod - mod / i)  * inv[mod % i] % mod;
}inline int C(int m, int n){if(n < m) return 0;return fac[n] * inv[fac[n - m]] % mod * inv[fac[m]] % mod;
}
inline int Lucas(int m, int n){if(n < m) return 0;if(n < mod && m < mod) return C(m, n);return Lucas(m / mod, n / mod) * Lucas(m % mod, n % mod) % mod;
}
int main(){
//FileOpen();Init();int Tasks;io >> Tasks;Init();while(Tasks--){int n, m;io >> n >> m;printf("%d\n", Lucas(m, n) % mod);}return 0;
}