【模板库】线段树合并

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=4530

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009; 
const int M = N * 21;

int n, m, vis[N], head[N], nxt[N], to[N];
int dep[N], beg[N], out[N], sz[N], fa[N];
struct Data{
	int t, x, y;
	inline Data() {
	}
	inline Data(bool a, int b, int c):t(a), x(b), y(c) {
	} 
}opt[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline void DFS(int w, int f) {
	static int D = 0;
	vis[w] = 1;
	beg[w] = ++D;
	dep[w] = dep[f] + 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	out[w] = D;
}

inline int find(int x) {
	return fa[x] == x? x: fa[x] = find(fa[x]);
}

class SegmentTree{
int cnt, ch[M][2], sum[M], root[N];
public:
	inline void insert(int p, int v) {
		insert(root[p], 1, n, v);
	}
	inline void merge(int a, int b) {
		root[a] = Merge(root[a], root[b]);
	}
	inline int query(int p, int l, int r) {
		return query(root[p], 1, n, l, r);
	}
private:
	inline int Merge(int a, int b) {
		if (!a || !b) {
			return a + b;
		} else {
			sum[a] += sum[b];
			ch[a][0] = Merge(ch[a][0], ch[b][0]);
			ch[a][1] = Merge(ch[a][1], ch[b][1]);
			return a;
		}
	}
	inline void insert(int &w, int l, int r, int p) {
		sum[w = ++cnt] = 1;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (p < mid) {
				insert(ch[w][0], l, mid - 1, p);
			} else {
				insert(ch[w][1], mid, r, p);
			}
		}
	} 
	inline int query(int w, int l, int r, int L, int R) {
		if (!w) {
			return 0;
		} else if (L <= l && r <= R) {
			return sum[w];
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			ret += L < mid? query(ch[w][0], l, mid - 1, L, R): 0;
			ret += mid <= R? query(ch[w][1], mid, r, L, R): 0;
			return ret;
		}
	}
}SGT;

int main() {
	n = read(); m = read();
	for (int i = 1; i <= m; i++) {
		char cmd[3]; 
		scanf("%s", cmd);
		int u = read(), v = read();
		if (cmd[0] == 'A') {
			AddEdge(u, v);
		}
		opt[i] = Data(cmd[0] == 'A', u, v);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			DFS(i, i);
		}
	}
	for (int i = 1; i <= n; i++) {
		sz[i] = 1;
		fa[i] = i;
		SGT.insert(i, beg[i]);
	}
	for (int i = 1; i <= m; i++) {
		int u = opt[i].x, v = opt[i].y;
		if (opt[i].t == 1) {
			SGT.merge(find(u), find(v));
			sz[find(u)] += sz[find(v)];
			fa[find(v)] = find(u);
		} else {
			if (dep[u] < dep[v]) {
				swap(u, v);
			}
			int p1 = SGT.query(find(u), beg[u], out[u]);
			int p2 = sz[find(u)] - p1;
			printf("%lld\n", (LL)p1 * p2);
		}
	}
	return 0;
}

【模板库】拉格朗日插值法

参考例题:http://oi.cyo.ng/?p=3191

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200;
const int MOD = 1000000007;

int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
} 

inline int Pow(int w, int t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		} 
	}
	return ret;
}

inline int LagrangePolynomial(int x, int len, int *ff, int *xx) {
	int ret = 0;
	for (int i=1;i<=len;i++) {
		int tmp = ff[i];
		for (int j=1;j<=len;j++) {
			if (i == j) continue;
			tmp = (LL)tmp * (x - xx[j]) % MOD;
			tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD;
		}
		ret = (ret + tmp) % MOD;
	}
	return (ret + MOD) % MOD;
} 

int main() {
	n = read(); m = read(); K = read();
	for (int i=1;i<=m;i++) {
		u[i] = read();
	}
	for (int i=1;i<=m;i++) {
		r[i] = read();
	}
	//预处理组合数 
	C[0][0] = 1;
	for (int i=1;i<=n;i++) {
		C[i][0] = 1;
		for (int j=1;j<=i;j++) {
			C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
		}
	}
	//拉格朗日插值
	for (int w=1;w<=m;w++) {
		for (int i=1;i<=n+1;i++) {
			f[i] = 0; h[i] = i;
			for (int j=1;j<=i;j++) {
				f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD;
			}
		}  
		g[w] = LagrangePolynomial(u[w], n+1, f, h);
	}
	//广义容斥原理 
	int ans = 0;
	for (int i=K,t=1;i<=n;i++,t*=-1) {
		alpha[i] = C[n-1][i];
		for (int j=1;j<=m;j++) {
			alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD;
		}
		ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD;
	}
	printf("%d\n",(ans+MOD)%MOD);
	return 0;
}

【模板库】半平面交

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=2618
参考资料:http://foenix.top/2015/03/17/半平面交nlogn方法小结/
备注:这份代码不能处理退化成一个点或一条线的情况,如果实在要处理这种情况,请自行将直线平移适当距离

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 10000;
const double EPS = 1e-8;

int n,m;

struct Point{
	double x,y;
	inline Point() {}
	inline Point(double a, double b):x(a),y(b) {}
	inline Point operator + (const Point &P) const {return Point(x+P.x, y+P.y);}
	inline Point operator - (const Point &P) const {return Point(x-P.x, y-P.y);}
	inline Point operator * (double d) const {return Point(x*d, y*d);}
	inline Point operator / (double d) const {return Point(x/d, y/d);}
	inline double operator * (const Point &P) const {return x*P.x + y*P.y;}
	inline double operator ^ (const Point &P) const {return x*P.y - P.x*y;} 
}p[N],cvx[N];

struct Line{
	Point a,b; double slp;
	inline Line() {}
	inline Line(const Point &x, const Point &y) {a = x; b = y; slp = atan2(b.y-a.y, b.x-a.x);}
	inline bool operator < (const Line &L) const {return slp < L.slp - EPS || (fabs(slp-L.slp) < EPS && ((b-a)^(L.b-a)) < -EPS);}
	inline bool operator != (const Line &L) {return fabs(slp - L.slp) > EPS;}
	inline bool onleft(const Point &P) {return ((b - a) ^ (P - a)) > EPS;}
	inline double len() {return sqrt((b - a) * (b - a));}
	inline Point ins(const Line &L) {
		double s1 = (b - L.b) ^ (L.a - L.b);
		double s2 = (a - L.a) ^ (L.b - L.a);
		Point tmp = a + (((b - a) * s2) / (s1 + s2));
		return a + (((b - a) * s2) / (s1 + s2));
	}
}l[N],que[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void HalfPlaneIntersection(int tot, Line *a, int &cnt, Line *b, Point *c) {
	sort(a+1, a+1+tot); cnt = tot; tot = 1; 
	for (int i=2;i<=cnt;i++) if (a[i] != a[i-1]) a[++tot] = a[i]; 
	b[1] = a[1]; b[2] = a[2]; int l=1,r=2;
	for (int i=3;i<=tot;i++) {
		while (l < r && !a[i].onleft(b[r-1].ins(b[r]))) r--;
		while (l < r && !a[i].onleft(b[l].ins(b[l+1]))) l++;
		b[++r] = a[i];
	} 
	while (l < r && !b[l].onleft(b[r].ins(b[r-1]))) r--;
	while (l < r && !b[r].onleft(b[l].ins(b[l+1]))) l++;
	cnt = 0; b[0] = b[r];
	for (int i=l;i<=r;i++) b[++cnt] = b[i];
	for (int i=1;i<=cnt;i++) c[i] = b[i].ins(b[i-1]); 
}

int main() {
	n = read(); int tot=0,cnt=0;
	for (int i=1;i<=n;i++) {
		m = read();
		for (int j=1;j<=m;j++) p[j].x = read(), p[j].y = read();
		p[m+1] = p[1];
		for (int j=1;j<=m;j++) l[++tot] = Line(p[j], p[j+1]);
	}
	HalfPlaneIntersection(tot, l, cnt, que, cvx);
	double vout = 0;
	for (int i=2;i<cnt;i++) vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]);
	printf("%.3lf\n",vout/2);
	return 0;
}

【模板库】二维凸包

参考例题:http://poj.org/problem?id=3348
备注:可以处理重点,坐标值可以是整数和小数

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;

const int N = 100000;
const double EPS = 1e-8;

int n,cnt;

struct Point{
	double x,y;
	inline Point() {}
	inline Point(double a, double b):x(a),y(b) {}
	inline Point operator + (const Point &A) {return Point(x+A.x, y+A.y);}
	inline Point operator - (const Point &A) {return Point(x-A.x, y-A.y);}
	inline Point operator / (double A) {return Point(x/A, y/A);}
	inline Point operator * (double A) {return Point(x*A, y*A);}
	inline double operator * (const Point &A) {return x*A.x + y*A.y;}
	inline double operator ^ (const Point &A) {return x*A.y - A.x*y;}
	inline bool operator < (const Point &B) const {return x < B.x - EPS || (fabs(x-B.x) < EPS && y < B.y - EPS);}
	inline bool operator == (const Point &B) const {return fabs(x - B.x) + fabs(y - B.y) < EPS;}
}p[N],cvx[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void ConvexHull(int tot, Point *a, int &sz, Point *ret) {
	if (!tot) {sz = 0; return;}
	sort(a+1, a+1+tot); ret[sz=1] = a[1];
	tot = unique(a+1, a+1+tot) - a - 1;
	for (int i=2;i<=tot;i++) {
		while (sz > 1 && ((ret[sz] - ret[sz-1]) ^ (a[i] - ret[sz])) < EPS) sz--;
		ret[++sz] = a[i];	
	}
	for (int i=tot-1,mn=sz;i>0;i--) {
		while (sz > mn && ((ret[sz] - ret[sz-1]) ^ (a[i] - ret[sz])) < EPS) sz--;
		ret[++sz] = a[i];
	} 
	sz -= sz > 2;
} 

int main() {
	n = read();
	for (int i=1;i<=n;i++) p[i].x = read(), p[i].y = read();
	ConvexHull(n, p, cnt, cvx);
	double vout = 0; 
	for (int i=2;i<cnt;i++) 
		vout += (cvx[i] - cvx[1]) ^ (cvx[i+1] - cvx[1]) / 2;
	printf("%d\n",(int)(vout/50));
	return 0;
}

【模板库】FWT

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=4589

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009; 
const int MOD = 1000000007;
const int REV = 500000004;

bool vis[N];
int arr[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

inline void FWT(int *a, int len, int opt = 1) {
	for (int d = 1; d < len; d <<= 1) {
		for (int i = 0; i < len; i += d << 1) {
			for (int j = 0; j < d; j++) {
				int t1 = a[i + j], t2 = a[i + j + d];
				//XOR
				if (opt == 1) {
					a[i + j] = (t1 + t2) % MOD;
					a[i + j + d] = (t1 - t2) % MOD;
				} else {
					a[i + j] = (LL)(t1 + t2) * REV % MOD;
					a[i + j + d] = (LL)(t1 - t2) * REV % MOD;
				}
				/*
				AND
				if (opt == 1) {
					arr[i + j] = t1 + t2;
					//arr[i + j + d] = t2;
				} else {
					arr[i + j] = t1 - r2;
					//arr[i + j + d] = t2;
				}
				*/
				/*
				OR
				if (opt == 1) {
					//arr[i + j] = t1;
					arr[i + j + d] = t2 + t1;
				} else {
					//arr[i + j] = t1;
					arr[i + j + d] = t2 - t1;
				}
				*/
			}
		}
	}
}

int main() {
	for (int n, m; ~scanf("%d %d", &n, &m); ) {
		memset(arr, 0, sizeof(arr));
		for (int i = 2; i <= m; i++) {
			if (!vis[i]) {
				arr[i] = 1;
				for (int j = i << 1; 0 <= j && j <= m; j += i) {
					vis[j] = 1;
				}
			}
		}
		int len = 1; 
		for (; len <= m; len <<= 1);
		FWT(arr, len);
		for (int i = 0; i < len; i++) {
			arr[i] = Pow(arr[i], n);
		}
		FWT(arr, len, -1);
		printf("%d\n", (arr[0] + MOD) % MOD);
	}
	return 0;
}

【模板库】Splay

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=1895

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int INF = 0x7fffffff;
const int N = 200009;
  
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
  
class Splay{
    struct Node{int ch[2],val,mn,sz,fa,delta,rev;}p[N]; int cnt;
    public:
        inline Splay() { //init the splay and place begining(1) and ending(2) of the sequence
            cnt = 2; p[1].ch[1] = 2;
            p[1].val = p[1].mn = INF;
            p[2].val = p[2].mn = INF;
            p[1].sz = 2; p[2].sz = 1;
            p[1].fa = p[2].fa = 1;
        }
        inline void insert(int pos, int v) { ++pos; //insert a new node with value v as ths (pos + 1) node
            int w; splay(w=rank(1, pos), 1);
            int nw; splay(nw=rank(1, pos+1), w);
            p[nw].ch[0] = ++cnt; p[cnt].fa = nw;
            p[cnt].mn = p[cnt].val = v; p[cnt].sz = 1;
            maintain(nw); maintain(w); maintain(1);
        }
        inline void add(int l, int r, int v) { ++l; ++r; //add value v to elements of range[l,r]
            int w; splay(w=rank(1, l-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[p[nw].ch[0]].delta += v; 
            PushDown(p[nw].ch[0]); maintain(nw);
            maintain(w); maintain(1); 
        }
        inline int query(int l, int r) { ++l; ++r; //query the min element in range[l,r]
            int w; splay(w=rank(1, l-1), 1); 
            int nw; splay(nw=rank(1, r+1), w);
            return PushDown(p[nw].ch[0]), p[p[nw].ch[0]].mn;
        }
        inline void remove(int r) { ++r; //remove the r node
            int w; splay(w=rank(1, r-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[nw].ch[0] = 0; maintain(nw);
            maintain(w); maintain(1);
        } 
        inline void reverse(int l, int r) { ++l; ++r; //reverse the elements in range[l,r]
            int w; splay(w=rank(1, l-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[p[nw].ch[0]].rev ^= 1;
        }
        inline void Rotate(int l, int r, int t) { //rotate the elements in range[l,r] t steps
            if (l==r||!(t%=((++r) - (++l) + 1))) return;
            int w; splay(w=rank(1, l-1), 1); 
            int nw; splay(nw=rank(1, r+1), w);
            int nnw; splay(nnw=rank(p[nw].ch[0], r-l-t+1), nw); 
            int nnnw; splay(nnnw=rank(p[nnw].ch[1], t), nnw); 
            p[nw].ch[0] = nnnw; p[nnnw].ch[1] = nnw; p[nnw].ch[1] = 0;
            p[nnw].fa = nnnw; p[nnnw].fa = nw;
            maintain(nnw); maintain(nnnw); 
        }
    private:
        inline void PushDown(int w) {
            if (p[w].delta) {
                p[w].mn += p[w].delta; p[w].val += p[w].delta;
                p[p[w].ch[1]].delta += p[w].delta;
                p[p[w].ch[0]].delta += p[w].delta;
                p[w].delta = 0;
            }
            if (p[w].rev) {
                swap(p[w].ch[0], p[w].ch[1]); p[w].rev = 0;
                p[p[w].ch[0]].rev ^= 1; p[p[w].ch[1]].rev ^= 1;
            }
        }
        inline void maintain(int w) {
            p[w].mn = p[w].val; p[w].sz = p[p[w].ch[0]].sz + p[p[w].ch[1]].sz + 1;
            if (p[w].ch[0]) PushDown(p[w].ch[0]), p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
            if (p[w].ch[1]) PushDown(p[w].ch[1]), p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn); 
        }
        inline void rotate(int w) { //rotate w to its father
            int f=p[w].fa,t=p[f].ch[1]==w,ff=p[f].fa; 
            p[f].ch[t] = p[w].ch[t^1]; p[p[w].ch[t^1]].fa = f;
            p[w].ch[t^1] = f; p[w].fa = p[f].fa; p[f].fa = w; 
            if (ff != f) p[ff].ch[p[ff].ch[1]==f] = w;
            maintain(f); maintain(w);
        }
        inline void splay(int w, int pur) { //splay w to pur's son
            if (w == pur) return;
            for (int f,ff;f=p[w].fa,p[w].fa!=pur;) {
                ((ff=p[f].fa) == pur)? rotate(w):
                (((p[f].ch[1]==w)^(p[ff].ch[1]==f))?rotate(w),rotate(f):rotate(f),rotate(w));
            }
        }
        int rank(int w, int t) { //function rank is needed to be called before each splay operation to push down tags
            PushDown(w); if (t<=0) return w; int szt = p[p[w].ch[0]].sz;
            if (szt >= t) return rank(p[w].ch[0], t);
            else if (szt + 1 == t) return w;
            else return rank(p[w].ch[1], t-1-szt);
        }
}SP; 
  
int main() {
    int n = read(); char opt[10]; 
    for (int i=1;i<=n;i++) SP.insert(i-1, read());
    for (int m=read(),l,r,x;m;--m) {
        scanf("%s",opt+1);
        if (opt[1] == 'A') {
            l = read(); r = read();
            SP.add(l, r, read());
        } else if (opt[1] == 'R' && opt[4] == 'E') {
            l = read(); r = read();
            SP.reverse(l, r);
        } else if (opt[1] == 'R') {
            l = read(); r = read();
            SP.Rotate(l, r, read());
        } else if (opt[1] == 'I') {
            l = read(); r = read();
            SP.insert(l, r);
        } else if (opt[1] == 'D') {
            SP.remove(read());
        } else {
            l = read(); r = read();
            printf("%d\n",SP.query(l,r));
        } 
    }
    return 0;
}

【模板库】原根

参考例题:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135
时间复杂度:能跑1e9
相关限制:此份代码仅能求素数的原根,合数的原根还需要求一个欧拉函数
参考代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline int Get_Primitive_Root(int w) {
    vector<int> pri;
    for (int i=2,lim=ceil(sqrt(w)),cur=w-1;i<lim;i++) {
        if (cur % i == 0) {
            pri.push_back(i);
            while (cur % i == 0) 
                cur /= i;
        }
        if (cur > 1 && i == lim - 1) 
            pri.push_back(cur);
    }
    static auto Pow = [](int w, int t, int MOD) {
        int ret = 1;
        for (;t;t>>=1,w=(LL)w*w%MOD) 
            if (t & 1) ret = (LL)ret * w % MOD;
        return ret;
    };
    if (!pri.size()) return 2;
    for (int i=2;i<=w;i++) {
        for (int j=pri.size()-1;~j;j--) {
            if (Pow(i,w/pri[j],w) == 1) break;
            if (!j) return i;
        }
    }
}
 
int main() {
    printf("%d\n",Get_Primitive_Root(read())); 
    return 0;
}

【模板库】一般图最大匹配

参考例题:http://uoj.ac/problem/79
参考代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 501;
const int MOD = 998244353;

int n,m;

class Maximum_Matchings_in_General_Graph{
	int a[N][N],b[N][N],G[N][N];
	int tot,pat[N],id[N],num[N];
	bool del_x[N],del_y[N];
	public:
		inline void Add_Edge(int u, int v) {
			G[u][v] = a[u][v] = rand() % (MOD - 1) + 1;
			G[v][u] = a[v][u] = -a[u][v];
		}
		inline int solve() {
			for (int i=1;i<=n;i++) id[i] = i;
			Gauss(n);
			for (int i=1;i<=n;i++) 
				if (a[id[i]][id[i]]) 
					num[++tot] = i;
			for (int i=1;i<=tot;i++)
				for (int j=1;j<=tot;j++) 
					a[i][j] = G[num[i]][num[j]];
			Gauss(tot, 1);
			for (int i=1;i<=tot;i++) {
				if (!del_x[i]) {
					for (int j=1;j<=tot;j++) {
						if (!del_x[j] && G[num[i]][num[j]] && b[i][j]) {
							pat[num[i]] = num[j];
							pat[num[j]] = num[i];
							Eliminat(i, j);
							Eliminat(j, i);
							break;
						}
					}
				}
			}
			return tot;
		}
		inline void print() {
			printf("%d\n",tot>>1);
			for (int i=1;i<=n;i++) 
				printf("%d ",pat[i]);
		}
	private:
		inline int Pow(int w, int t) {
			int ret = 1;
			for (;t;t>>=1,w=(LL)w*w%MOD)
				if (t & 1) ret = (LL)ret * w % MOD;
			return ret;
		}
		inline void Gauss(int sz, bool I = 0) {
			for (int i=1;i<=sz;++i) b[i][i] = 1;
			for (int i=1;i<=sz;++i) {
				for (int j=i;j<=sz;++j) {
					if (a[j][i]) {
						swap(id[i], id[j]);
						swap(a[i], a[j]);
						if (I) swap(b[i], b[j]);
						break;
					}
				}
				if (!a[i][i]) continue;
				int inv = Pow(a[i][i], MOD - 2);
				for (int j=1;j<=sz;++j) if (a[i][j]) a[i][j] = (LL)a[i][j] * inv % MOD;
				if (I) for (int j=1;j<=sz;++j) if (b[i][j]) b[i][j] = (LL)b[i][j] * inv % MOD;
				for (int j=1;j<=sz;++j) {
					if (j != i && a[j][i]) {
						LL tmp = a[j][i];
						for (int k=1;k<=sz;++k) if (a[i][k]) a[j][k] = (a[j][k] - tmp * a[i][k]) % MOD;
						if (I) for (int k=1;k<=sz;++k) if (b[i][k]) b[j][k] = (b[j][k] - tmp * b[i][k]) % MOD;	
					}
				}
			}
		}
		inline void Eliminat(int x, int y) {
			del_x[x] = del_y[y] = 1;
			LL inv = Pow(b[x][y], MOD - 2);
			for (int i=1;i<=tot;++i) {
				if (!del_y[i]) {
					LL tmp = b[x][i] * inv % MOD;
					for (int j=1;j<=tot;++j) {
						if (!del_x[j] && b[y][j]) {
							b[i][j] = (b[i][j] - tmp * b[y][j]) % MOD;			
						}
					}
				}
			}
		}
}MMGG;

inline char Read(){
	static const int BUF_SIZE = 1000000; 
	static char buf[BUF_SIZE],*p1=0,*p2=0;
    if (p1 == p2){
    	p1=buf; p2=buf+fread(buf,1,BUF_SIZE,stdin);
		if (p2==p1) return -1;
    } return *p1++;
} 

inline int read(){
	char c=Read(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=Read();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=Read();}
	return ret*f;
}

int main() {
	srand(19260817);
   	n = read(); m = read();
   	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		MMGG.Add_Edge(u, v);
	}
	MMGG.solve();
	MMGG.print();
	return 0;
}

【模板库】树上点分治

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=1468
参考代码:

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 40000 + 9;
const int M = N << 1;

int head[N],nxt[M],to[M],cost[M]; 
int n,k,vout;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
} 

inline void Add_Edge(int u, int v, int w) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

namespace Node_Decomposition{
	#define ND Node_Decomposition
	const int INF = 10000000;
	int vis[N],dep[N],sum[N];
	int tot,cur,num_node,root;

	void Get_Root(int w, int f) {
		int mx = 0; sum[w] = 1;
		for (int i=head[w];i;i=nxt[i]) {
			if (to[i] != f && !vis[to[i]]) {
				Get_Root(to[i], w);
				mx = max(mx, sum[to[i]]);
				sum[w] += sum[to[i]];
			}
		}
		mx = max(mx, num_node - mx);
		if (mx < cur) root = w, cur = mx;
	}

	void Get_Dep(int w, int f, int bas) {
		for (int i=head[w];i;i=nxt[i]) {
			if (to[i] != f && !vis[to[i]]) {
				dep[++tot] = bas + cost[i];
				Get_Dep(to[i], w, dep[tot]);
			}
		}
	}

	inline int cal(int w, int bas) {
		dep[tot=1] = bas;
		Get_Dep(w, w, bas);
		sort(dep+1, dep+1+tot);
		int r = tot, l = 1, ret = 0;
		while (l < r) {
			while (l < r && dep[l] + dep[r] > k) r--;
			ret += r - l++;
		}
		return ret;
	}

	void solve(int w, int sz) {
		vis[w] = 1; 
		vout += cal(w, 0);
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				vout -= cal(to[i], cost[i]);
				num_node = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
				cur = INF; Get_Root(to[i], w);
				solve(root, num_node);
			}
		}
	}
	
	void solve() {
		num_node = n; cur = INF; 
		Get_Root(1, 1);
		solve(root, n);
	}
}; 

int main() {
	n = read();
	for (int i=1,u,v,w;i<n;i++) {
		u = read(); v = read(); w = read();
		Add_Edge(u, v, w);
	}
	k = read();
	ND::solve();
	printf("%d",vout);
	return 0;
}

【模板库】最强流读入

这是我见过的,最强的输入输出库
没有之一

namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    //fread->read
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
            //{printf("IO error!\n");system("pause");for (;;);exit(0);}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(double &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (ch=='.'){
            double tmp=1; ch=nc();
            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if (sign)x=-x;
    }
    inline void read(char *s){
        char ch=nc();
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
    }
    inline void read(char &c){
        for (c=nc();blank(c);c=nc());
        if (IOerror){c=-1;return;}
    }
    //getchar->read
    inline void read1(int &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(ll &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(double &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (ch=='.'){
            double tmp=1;
            for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
        }
        if (bo)x=-x;
    }
    inline void read1(char *s){
        char ch=getchar();
        for (;blank(ch);ch=getchar());
        for (;!blank(ch);ch=getchar())*s++=ch;
        *s=0;
    }
    inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
    //scanf->read
    inline void read2(int &x){scanf("%d",&x);}
    inline void read2(ll &x){
        #ifdef _WIN32
            scanf("%I64d",&x);
        #else
        #ifdef __linux
            scanf("%lld",&x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void read2(double &x){scanf("%lf",&x);}
    inline void read2(char *s){scanf("%s",s);}
    inline void read2(char &c){scanf(" %c",&c);}
    inline void readln2(char *s){gets(s);}
    //fwrite->write
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        void out(char ch){
            if (p1==pend){
                fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
            }
            *p1++=ch;
        }
        void print(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(double x,int y){
            static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
                1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if (x<-1e-12)out('-'),x=-x;x*=mul[y];
            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
            if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
        }
        void println(double x,int y){print(x,y);out('\n');}
        void print(char *s){while (*s)out(*s++);}
        void println(char *s){while (*s)out(*s++);out('\n');}
        void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    //puts->write
    char Out[OUT_SIZE],*o=Out;
    inline void print1(int x){
        static char buf[15];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(int x){print1(x);*o++='\n';}
    inline void print1(ll x){
        static char buf[25];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(ll x){print1(x);*o++='\n';}
    inline void print1(char c){*o++=c;}
    inline void println1(char c){*o++=c;*o++='\n';}
    inline void print1(char *s){while (*s)*o++=*s++;}
    inline void println1(char *s){print1(s);*o++='\n';}
    inline void println1(){*o++='\n';}
    inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
    struct puts_write{
        ~puts_write(){flush1();}
    }_puts;
    inline void print2(int x){printf("%d",x);}
    inline void println2(int x){printf("%d\n",x);}
    inline void print2(char x){printf("%c",x);}
    inline void println2(char x){printf("%c\n",x);}
    inline void print2(ll x){
        #ifdef _WIN32
            printf("%I64d",x);
        #else
        #ifdef __linux
            printf("%lld",x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void println2(ll x){print2(x);printf("\n");}
    inline void println2(){printf("\n");}
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};

看了这份代码以后,我觉得一切语言都是苍白的

—————————— UPD 2017.7.5 ——————————
日常卡常用的话,用下面这份代码就好

inline char Read(){
    static const int BUF_SIZE = 1000000; 
    static char buf[BUF_SIZE], *p1 = 0, *p2 = 0;
    if (p1 == p2){
		p2 = (p1 = buf) + fread(buf, 1, BUF_SIZE, stdin);
    } 
	return p1 == p2? -1: *p1++;
} 
 
inline int read() {
	char c = Read(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = Read());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = Read());
	return ret * f;
}

【模板库】斜堆

参考题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2809
参考代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;

LL vout;
int led[N],n,m,arr[N],rt;
vector<int> G[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

namespace Skew_Heap{
	#define SHP Skew_Heap
	int ch[N][2],sz[N],val[N],root[N],cnt;
	LL sum[N];
	
	inline void maintain(int w) {
		sz[w] = sz[ch[w][0]] + sz[ch[w][1]] + 1;
		sum[w] = sum[ch[w][0]] + sum[ch[w][1]] + val[w];
	}
	
	int Merge(int a, int b){
		if (!a || !b) return a+b;
		else {
			if (val[b] > val[a]) swap(a,b);
			ch[a][1] = Merge(ch[a][1],b);
			swap(ch[a][0],ch[a][1]); maintain(a); 
			return a;
		}
	}
	
	inline void pop(int w){
		root[w] = Merge(ch[root[w]][0],ch[root[w]][1]);
	}
	
	inline void insert(int w, int v){
		val[++cnt] = sum[cnt] = v; sz[cnt] = 1;
		root[w] = Merge(root[w],cnt);
	}
};

int main(){
	using namespace Skew_Heap;
	n = read(); m = read();
	for (int i=1,tmp;i<=n;i++) {
		G[read()].push_back(i);
		arr[i] = read(); led[i] = read();
	}
	for (int i=n;i;i--) {
		for (int j=0,lim=G[i].size();j<lim;j++) root[i] = Merge(root[i],root[G[i][j]]);
		insert(i,arr[i]); while (root[i] && sum[root[i]] > m) pop(i);
		vout = max(vout,(LL)sz[root[i]]*led[i]);
	} 
	printf("%lld\n",vout);
	return 0;
}

【模板库】Fenwick Tree RMQ version

参考例题:http://acm.split.hdu.edu.cn/showproblem.php?pid=1754
参考代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 200000+9;
const int INF = 1000000000;

int n,m;
char pat[10];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&(-(x)))
	int MX[N],arr[N];
	
	inline void init(){
		for (int i=1;i<=n;i++)
			MX[i] = -INF;
	}
	
	inline void modify(int pos, int val){
		int pre = arr[pos]; arr[pos] = val;
		if (val >= pre) {
			for (int i=pos;i<=n;i+=lowbit(i)) 
				MX[i] = max(MX[i],val);
		} else {
			for (int i=pos;i<=n;i+=lowbit(i)) {
				MX[i] = arr[i];
				for (int j=lowbit(i)/2;j;j>>=1) 
					MX[i] = max(MX[i],MX[i-j]);
			}
		}
	}
	
	inline int query(int l, int r) {
		int ret = -INF;
		while (r >= l) {
			if (r-lowbit(r)+1 >= l) ret = max(ret, MX[r]), r -= lowbit(r);
			else ret = max(ret, arr[r]), r--;
		}
		return ret;
	}
};

int main(){
	while (~scanf("%d%d",&n,&m)) {
		BIT::init();
		for (int i=1;i<=n;i++) BIT::modify(i,read());	
		for (int i=1,l,r;i<=m;i++) {
			scanf("%s",pat+1);
			if (pat[1] == 'Q') l = read(), r = read(), printf("%d\n",BIT::query(l,r));
			else l = read(), r = read(), BIT::modify(l, r); 
		}
	}
	return 0;
}

【模板库】Borůvka’s algorithm

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=2429
参考代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define pow(x) ((x)*(x))
using namespace std;

const int N = 1000+9;
const int M = 1000000+9;
const double EPS = 1e-8;

int X[N],Y[N],to[M],nxt[M],head[N],val[N],tot,n,m,vout,fa[N],cot[N];
double w[M],cpt[N],MX;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int i, int j){
	double tmp = sqrt(pow(X[i]-X[j])+pow(Y[i]-Y[j]));
	to[++m] = j; nxt[m] = head[i]; w[m] = tmp; head[i] = m;
	to[++m] = i; nxt[m] = head[j]; w[m] = tmp; head[j] = m;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline void Boruvka(){
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int t=n;t>1;) {
		memset(cot,0,sizeof(cot));
		for (int i=1,f1,f2;i<=n;i++) for (int j=head[i];j;j=nxt[j]){
			f1 = find(i); f2 = find(to[j]);
			if (f1 != f2) {
				if (!cot[f1] || cpt[f1] > w[j]) cot[f1] = f2, cpt[f1] = w[j];
				if (!cot[f2] || cpt[f2] > w[j]) cot[f2] = f1, cpt[f2] = w[j];
			} 	
		}
		
		for (int i=1,ft;i<=n;i++) if (fa[i] == i) {
			if ((ft = find(cot[i])) != i) {
				fa[ft] = i; MX = max(MX, cpt[i]); t--;
			}
		} 
	}
}

int main(){
	tot=read(); for (int i=1;i<=tot;i++) val[i] = read();
	n = read(); for (int i=1;i<=n;i++) {
		X[i] = read(); Y[i] = read();
		for (int j=1;j<i;j++) AddEdge(i,j);
	}
	Boruvka();
	for (int i=1;i<=tot;i++) if (EPS+val[i] >= MX) vout++;
	printf("%d\n",vout);
	return 0;
}

算法简介:https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm
算法正确性证明:http://oi.cyo.ng/wp-content/uploads/2016/08/02345678641.png
国外带注释模板:http://www.geeksforgeeks.org/greedy-algorithms-set-9-boruvkas-algorithm/

【模板库】对拍

我之前一直是用.bat文件进行对拍,代码如下:

@echo off
:rep
echo running SJ.exe
SJ.exe > 11input.in
echo running bc.exe
bc.exe < 11input.in > 12bc.out
echo running me.exe
me.exe < 11input.in > 12me.out
fc 12me.out 12bc.out > nul
if not errorlevel 1 goto rep

但有一个我很想实现的功能:对拍时显示运行时间
于是今天考试的时候折腾了一下,搞出了下面这个东西:

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<windows.h>
using namespace std;

int main(){
	time_t a,b;
	while (true) {
		system("SJ.exe > 11input.in");
		
		a = clock();
		system("bc.exe < 11input.in > 12bc.out");
		b = clock(); printf("bc.exe cost %dms\n",b-a); 
		
		a = clock();
		system("me.exe < 11input.in > 12me.out");
		b = clock(); printf("me.exe cost %dms\n",b-a); 
		
		int tmp = system("fc 12bc.out 12me.out > result.txt");
		if (tmp == 1) system("taskkill /F /IM check.exe");
		cout<<endl<<endl;
	}
	return 0;
}

主要是应用了clock()和system()函数
要背住的东西也只有:”taskkill /F /IM check.exe”
运行效果如下:
check_cpp
感觉很不错,用了多少时间一目了然
因为调用了system()所以时间不是特别准,需要减去20ms的样子

【模板库】仙人掌生成

生成仙人掌,输出最短路的询问

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<vector>
using namespace std;

const int N = 10000;
const int Q = 10000;
const int INF = 10000;
const int block = 200;
const int MAXN = 100000;

int ord[MAXN],tmp,cnt,TMP;
vector<pair<int,int> > que;

inline int R(int lim) {
	if (!lim) return 0;
	else return rand()%lim+1;
}

int main(){
	srand(time(0));
	int n = N, q=R(Q);
	for (int i=1;i<=n;i++) ord[i] = i;
 	for (int i=1;i<=n;i++) swap(ord[R(n)],ord[R(n)]);
 	for (int i=1;i<=n;) {
		int len = min(R(n/block)+2,n-i+1);
		for (int j=0;j<len-1;j++) que.push_back(make_pair(ord[i+j],ord[i+j+1]));
		if (len > 2) que.push_back(make_pair(ord[i],ord[i+len-1]));
		if (tmp) que.push_back(make_pair(ord[i+R(len)-1],tmp));
		tmp = ord[i+R(len)-1]; i += len; 
	} cnt = que.size();
	printf("%d %d %d\n",n,cnt,q);
	for (int i=0;i<cnt;i++) {
		int a = que[i].first;
		int b = que[i].second;
		int c = R(INF);
		printf("%d %d %d\n",a,b,c);
	}
	for (int i=1;i<=q;i++) 
		cout<<R(n)<<' '<<R(n)<<endl;
	return 0;
}