欧拉函数模板
//直接求解欧拉函数 int euler(int n){ //返回euler(n) int res=n,a=n; for(int i=2;i*i<=a;i++){ if(a%i==0){ res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出 while(a%i==0) a/=i; } } if(a>1) res=res/a*(a-1); return res; } //筛选法打欧拉函数表 #define Max 1000001 int euler[Max]; void Init(){ euler[1]=1; for(int i=2;i<Max;i++) euler[i]=i; for(int i=2;i<Max;i++) if(euler[i]==i) for(int j=i;j<Max;j+=i) euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出 }
扩展欧几里得
long long ex_gcd(long long a, long long b, long long &x, long long &y){ if(b == 0){ x = 1, y= 0; return a; }else{ long long r = ex_gcd(b, a% b, y, x); y -= x*(a/b); return r; } }
dinic网络流
src：源点
sink：汇点
#include<queue> #include<iostream> #include<string.h> #include<stdio.h> using namespace std; const int inf = 1000000000; const int maxn = 20000, maxm = 500000; struct Edge{ int v, f, nxt; }; int src, sink; int g[maxn + 10]; int nume; Edge e[maxm*2+10]; void addedge(int u, int v, int c){ e[++nume].v = v; e[nume].f = c; e[nume].nxt = g[u]; g[u] = nume; e[++nume].v = u; e[nume].f = 0; e[nume].nxt = g[v]; g[v] = nume; } void init(){ memset(g, 0, sizeof(g)); nume = 1; } queue<int> que; bool vis[maxn +10]; int dist[maxn + 10]; void bfs(){ memset(dist, 0, sizeof(dist)); while(!que.empty()) que.pop(); vis[src] = 1; que.push(src); while(!que.empty()){ int u = que.front(); que.pop(); for(int i = g[u]; i; i = e[i].nxt) if(e[i].f && !vis[e[i].v]){ que.push(e[i].v); dist[e[i].v] = dist[u] + 1; vis[e[i].v] = true; } } } int dfs(int u, int delta){ if(u == sink){ return delta; }else{ int ret = 0; for(int i = g[u]; delta && i; i = e[i].nxt){ if(e[i].f && dist[e[i].v] == dist[u] +1){ int dd = dfs(e[i].v, min(e[i].f, delta)); e[i].f -= dd; e[i^1].f += dd; delta -= dd; ret += dd; } } return ret; } } int maxflow(){ int ret = 0; while(true){ memset(vis, 0, sizeof(vis)); bfs(); if(!vis[sink])return ret; ret += dfs(src, inf); } return ret; } int main(){ int n, m; while(scanf("%d%d", &n, &m)!=EOF){ init(); src = 1; sink = m; for(int i = 0; i < n; i++){ int x, y, z; scanf("%d%d%d", &x, &y, &z); addedge(x, y, z); } printf("%d ", maxflow()); } }
ac自动机
#include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> #include<queue> using namespace std; const int maxa = 500000; const int cha = 26; int n, m, k; struct Tire{ int next[maxa][cha], fail[maxa], end[maxa]; int root, L; int newnode(){ for(int i = 0; i < cha; i++){ next[L][i] = -1; } end[L++] = 0; return L-1; } void init(){ L = 0; root = newnode(); } void insert(char buf[]){ int len = strlen(buf); int now = root; for(int i = 0; i < len; i++){ if(next[now][buf[i] - 'a'] == -1) next[now][buf[i]-'a'] = newnode(); now = next[now][buf[i]-'a']; //printf("%d ", now); }//puts(""); end[now] ++; } void build(){ queue<int>Q; fail[root] = root; for(int i = 0; i < cha; i++){ if(next[root][i] == -1) next[root][i] = root; else{ fail[next[root][i]] = root; Q.push(next[root][i]); } } while(!Q.empty()){ int now = Q.front(); Q.pop(); // end[now] |= end[fail[now]]; for(int i = 0; i < cha; i++){ if(next[now][i] == -1) next[now][i] = next[fail[now]][i]; else{ fail[next[now][i]] = next[fail[now]][i]; Q.push(next[now][i]); // printf("**%d %d ",next[now][i],next[fail[now]][i]); } } } } int solve(char *s){ int ans = 0, k = 0; for(int i = 0; s[i]; i++){ int t = s[i] - 'a'; k = next[k][t]; int j = k; while(j){ ans += end[j]; //if(end[j]) printf("%d ",j); end[j] = 0; j = fail[j]; }//puts(""); } return ans; } }; char buf[1000005]; Tire ac; int main(){ int t, n; scanf("%d", &t); while(t--){ scanf("%d", &n); ac.init(); //memset(ac.end, 0, sizeof(ac.end)); for(int i = 0; i < n; i++){ scanf("%s", buf); ac.insert(buf); } ac.build(); scanf("%s", buf); printf("%d ", ac.solve(buf)); } } /* abcdefg bcdefg cdef de e ssaabcdefg */
凸包
#include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<algorithm> using namespace std; const int maxa = 1005; struct edge{ int x, y; }e[maxa], q[maxa]; int cmp(edge a, edge b){ if(a.x != b.x) return a.x < b.x; return a.y < b.y; } int det(int x1, int y1, int x2, int y2){ return x1*y2 - x2*y1; } int cross(edge a, edge b, edge c, edge d){ return det(b.x - a.x, b.y -a.y, d.x - c.x, d.y - c.y); } int make_tubao(int n){ sort(e, e+n, cmp); int m = 0; for(int i = 0; i < n; i++){ while(m >= 2 && cross(q[m-2], q[m-1], q[m-1], e[i])>= 0){ m--; } q[m++] = e[i]; } int k = m; for(int i = n-2; i >= 0; i--){ while(m > k && cross(q[m-2], q[m-1], q[m-1], e[i])>= 0){ m--; } q[m++] = e[i]; } return m; } double dis(edge a, edge b){ return sqrt((b.x - a.x)*(b.x - a.x) + (b.y-a.y)*(b.y-a.y)); } int print(int n, int m){ n = make_tubao(n); double ans = 0; for(int i = 0;i < n-1; i++){ // printf("%d %d ", q[i].x, q[i].y); ans += dis(q[i], q[i+1]); } printf("%.0f ", ans + 3.1415926*2*m); } int main(){ int n, m; while(scanf("%d%d", &n, &m)!=EOF){ for(int i = 0 ; i < n; i++){ scanf("%d%d", &e[i].x, &e[i].y); } print(n, m); } }
rmq
#include<iostream> #include<string.h> #include<stdio.h> using namespace std; const int maxa = 50005; int rmp_max[maxa][100]; int rmp_min[maxa][100]; int log(int n){ int cnt = 0; while(n){ cnt ++; n /= 2; } return cnt - 1; } int main(){ int n, m; while(scanf("%d%d", &n ,&m)!=EOF){ for(int i = 0;i < n; i++){ scanf("%d", &rmp_max[i][0]); rmp_min[i][0] = rmp_max[i][0]; } int l = log(n); for(int i = 1; i <= l; i++){ for(int j = 0; j+(1<<(i-1)) < n; j++){ rmp_max[j][i] = max(rmp_max[j][i-1], rmp_max[j+(1<<(i-1))][i-1]); rmp_min[j][i] = min(rmp_min[j][i-1], rmp_min[j+(1<<(i-1))][i-1]); } } while(m--){ int a, b; scanf("%d%d", &a, &b); a--, b--; int j = log(b-a+1); int maxn = max(rmp_max[a][j], rmp_max[b-(1<<j)+1][j]); int minn = min(rmp_min[a][j], rmp_min[b-(1<<j)+1][j]); printf("%d ", maxn-minn); } } }
后缀数组
height[i]存放的是排名第i的后缀与排名第i-1的后缀的最长前缀， sa[i]存的是排名第i的后缀是第几位开头的 rk[i]存放第i个位置开头的后缀的字典序排名 #include<iostream> #include<string.h> #include<stdio.h> using namespace std; #define rep(i,n) for(int i = 0;i < n; i++) using namespace std; const int size = 200005,INF = 1<<30; int rk[size],sa[size],height[size],w[size],wa[size],res[size]; void getSa (int len,int up) { int *k = rk,*id = height,*r = res, *cnt = wa rep(i,up) cnt[i] = 0; rep(i,len) cnt[k[i] = w[i]]++; rep(i,up) cnt[i+1] += cnt[i]; for(int i = len - 1; i >= 0; i--) { sa[--cnt[k[i]]] = i; } int d = 1,p = 0; while(p < len){ for(int i = len - d; i < len; i++) id[p++] = i; rep(i,len) if(sa[i] >= d) id[p++] = sa[i] - d; rep(i,len) r[i] = k[id[i]]; rep(i,up) cnt[i] = 0; rep(i,len) cnt[r[i]]++; rep(i,up) cnt[i+1] += cnt[i]; for(int i = len - 1; i >= 0; i--) { sa[--cnt[r[i]]] = id[i]; } swap(k,r); p = 0; k[sa[0]] = p++; rep(i,len-1) { if(sa[i]+d < len && sa[i+1]+d <len &&r[sa[i]] == r[sa[i+1]]&& r[sa[i]+d] == r[sa[i+1]+d]) k[sa[i+1]] = p - 1; else k[sa[i+1]] = p++; } if(p >= len) return ; d *= 2,up = p, p = 0; } } void getHeight(int len) { rep(i,len) rk[sa[i]] = i; height[0] = 0; for(int i = 0,p = 0; i < len - 1; i++) { int j = sa[rk[i]-1]; while(i+p < len&& j+p < len&& w[i+p] == w[j+p]) { p++; } height[rk[i]] = p; p = max(0,p - 1); } } int getSuffix(char s[]) { int len = strlen(s),up = 0; for(int i = 0; i < len; i++) { w[i] = s[i]; up = max(up,w[i]); } w[len++] = 0; getSa(len,up+1); getHeight(len); return len; }const int maxa = 100000*2+1; char str[maxa]; int main(){ while(scanf("%s", str)!=EOF){ int l = strlen(str); str[l] = ' '; scanf("%s", str+l+1); getSuffix(str); int ans = 0; int L = strlen(str); for(int i = 1;i < L; i++){ if((sa[i-1] < l && sa[i] > l) || (sa[i-1] > l && sa[i] < l)){ ans = max(ans, height[i]); } } printf("%d ", ans); } } /* abcde bcde */
汇总
欧拉函数模板 //直接求解欧拉函数 int euler(int n){ //返回euler(n) int res=n,a=n; for(int i=2;i*i<=a;i++){ if(a%i==0){ res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出 while(a%i==0) a/=i; } } if(a>1) res=res/a*(a-1); return res; } //筛选法打欧拉函数表 #define Max 1000001 int euler[Max]; void Init(){ euler[1]=1; for(int i=2;i<Max;i++) euler[i]=i; for(int i=2;i<Max;i++) if(euler[i]==i) for(int j=i;j<Max;j+=i) euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出 } 扩展欧几里得 long long ex_gcd(long long a, long long b, long long &x, long long &y){ if(b == 0){ x = 1, y= 0; return a; }else{ long long r = ex_gcd(b, a% b, y, x); y -= x*(a/b); return r; } } dinic网络流 src：源点 sink：汇点 #include<queue> #include<iostream> #include<string.h> #include<stdio.h> using namespace std; const int inf = 1000000000; const int maxn = 20000, maxm = 500000; struct Edge{ int v, f, nxt; }; int src, sink; int g[maxn + 10]; int nume; Edge e[maxm*2+10]; void addedge(int u, int v, int c){ e[++nume].v = v; e[nume].f = c; e[nume].nxt = g[u]; g[u] = nume; e[++nume].v = u; e[nume].f = 0; e[nume].nxt = g[v]; g[v] = nume; } void init(){ memset(g, 0, sizeof(g)); nume = 1; } queue<int> que; bool vis[maxn +10]; int dist[maxn + 10]; void bfs(){ memset(dist, 0, sizeof(dist)); while(!que.empty()) que.pop(); vis[src] = 1; que.push(src); while(!que.empty()){ int u = que.front(); que.pop(); for(int i = g[u]; i; i = e[i].nxt) if(e[i].f && !vis[e[i].v]){ que.push(e[i].v); dist[e[i].v] = dist[u] + 1; vis[e[i].v] = true; } } } int dfs(int u, int delta){ if(u == sink){ return delta; }else{ int ret = 0; for(int i = g[u]; delta && i; i = e[i].nxt){ if(e[i].f && dist[e[i].v] == dist[u] +1){ int dd = dfs(e[i].v, min(e[i].f, delta)); e[i].f -= dd; e[i^1].f += dd; delta -= dd; ret += dd; } } return ret; } } int maxflow(){ int ret = 0; while(true){ memset(vis, 0, sizeof(vis)); bfs(); if(!vis[sink])return ret; ret += dfs(src, inf); } return ret; } int main(){ int n, m; while(scanf("%d%d", &n, &m)!=EOF){ init(); src = 1; sink = m; for(int i = 0; i < n; i++){ int x, y, z; scanf("%d%d%d", &x, &y, &z); addedge(x, y, z); } printf("%d ", maxflow()); } }ac自动机 #include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> #include<queue> using namespace std; const int maxa = 500000; const int cha = 26; int n, m, k; struct Tire{ int next[maxa][cha], fail[maxa], end[maxa]; int root, L; int newnode(){ for(int i = 0; i < cha; i++){ next[L][i] = -1; } end[L++] = 0; return L-1; } void init(){ L = 0; root = newnode(); } void insert(char buf[]){ int len = strlen(buf); int now = root; for(int i = 0; i < len; i++){ if(next[now][buf[i] - 'a'] == -1) next[now][buf[i]-'a'] = newnode(); now = next[now][buf[i]-'a']; //printf("%d ", now); }//puts(""); end[now] ++; } void build(){ queue<int>Q; fail[root] = root; for(int i = 0; i < cha; i++){ if(next[root][i] == -1) next[root][i] = root; else{ fail[next[root][i]] = root; Q.push(next[root][i]); } } while(!Q.empty()){ int now = Q.front(); Q.pop(); // end[now] |= end[fail[now]]; for(int i = 0; i < cha; i++){ if(next[now][i] == -1) next[now][i] = next[fail[now]][i]; else{ fail[next[now][i]] = next[fail[now]][i]; Q.push(next[now][i]); // printf("**%d %d ",next[now][i],next[fail[now]][i]); } } } } int solve(char *s){ int ans = 0, k = 0; for(int i = 0; s[i]; i++){ int t = s[i] - 'a'; k = next[k][t]; int j = k; while(j){ ans += end[j]; //if(end[j]) printf("%d ",j); end[j] = 0; j = fail[j]; }//puts(""); } return ans; } }; char buf[1000005]; Tire ac; int main(){ int t, n; scanf("%d", &t); while(t--){ scanf("%d", &n); ac.init(); //memset(ac.end, 0, sizeof(ac.end)); for(int i = 0; i < n; i++){ scanf("%s", buf); ac.insert(buf); } ac.build(); scanf("%s", buf); printf("%d ", ac.solve(buf)); } } /* abcdefg bcdefg cdef de e ssaabcdefg */ 凸包 #include<iostream> #include<stdio.h> #include<string.h> #include<cmath> #include<algorithm> using namespace std; const int maxa = 1005; struct edge{ int x, y; }e[maxa], q[maxa]; int cmp(edge a, edge b){ if(a.x != b.x) return a.x < b.x; return a.y < b.y; } int det(int x1, int y1, int x2, int y2){ return x1*y2 - x2*y1; } int cross(edge a, edge b, edge c, edge d){ return det(b.x - a.x, b.y -a.y, d.x - c.x, d.y - c.y); } int make_tubao(int n){ sort(e, e+n, cmp); int m = 0; for(int i = 0; i < n; i++){ while(m >= 2 && cross(q[m-2], q[m-1], q[m-1], e[i])>= 0){ m--; } q[m++] = e[i]; } int k = m; for(int i = n-2; i >= 0; i--){ while(m > k && cross(q[m-2], q[m-1], q[m-1], e[i])>= 0){ m--; } q[m++] = e[i]; } return m; } double dis(edge a, edge b){ return sqrt((b.x - a.x)*(b.x - a.x) + (b.y-a.y)*(b.y-a.y)); } int print(int n, int m){ n = make_tubao(n); double ans = 0; for(int i = 0;i < n-1; i++){ // printf("%d %d ", q[i].x, q[i].y); ans += dis(q[i], q[i+1]); } printf("%.0f ", ans + 3.1415926*2*m); } int main(){ int n, m; while(scanf("%d%d", &n, &m)!=EOF){ for(int i = 0 ; i < n; i++){ scanf("%d%d", &e[i].x, &e[i].y); } print(n, m); } } rmq #include<iostream> #include<string.h> #include<stdio.h> using namespace std; const int maxa = 50005; int rmp_max[maxa][100]; int rmp_min[maxa][100]; int log(int n){ int cnt = 0; while(n){ cnt ++; n /= 2; } return cnt - 1; } int main(){ int n, m; while(scanf("%d%d", &n ,&m)!=EOF){ for(int i = 0;i < n; i++){ scanf("%d", &rmp_max[i][0]); rmp_min[i][0] = rmp_max[i][0]; } int l = log(n); for(int i = 1; i <= l; i++){ for(int j = 0; j+(1<<(i-1)) < n; j++){ rmp_max[j][i] = max(rmp_max[j][i-1], rmp_max[j+(1<<(i-1))][i-1]); rmp_min[j][i] = min(rmp_min[j][i-1], rmp_min[j+(1<<(i-1))][i-1]); } } while(m--){ int a, b; scanf("%d%d", &a, &b); a--, b--; int j = log(b-a+1); int maxn = max(rmp_max[a][j], rmp_max[b-(1<<j)+1][j]); int minn = min(rmp_min[a][j], rmp_min[b-(1<<j)+1][j]); printf("%d ", maxn-minn); } } }
组合数取模
1 <= n, m <= 1e18 mod < 1000000 #include <iostream> #include <string.h> #include <stdio.h> using namespace std; typedef long long LL; LL n,m,p; LL quick_mod(LL a, LL b) { LL ans = 1; a %= p; while(b) { if(b & 1) { ans = ans * a % p; b--; } b >>= 1; a = a * a % p; } return ans; } LL C(LL n, LL m) { if(m > n) return 0; LL ans = 1; for(int i=1; i<=m; i++) { LL a = (n + i - m) % p; LL b = i % p; ans = ans * (a * quick_mod(b, p-2) % p) % p; } return ans; } LL Lucas(LL n, LL m) { if(m == 0) return 1; return C(n % p, m % p) * Lucas(n / p, m / p) % p; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%I64d%I64d%I64d", &n, &m, &p); printf("%I64d ", Lucas(n,m)); } return 0; }
最大流sap模板
#include<iostream> #include<stdio.h> #include<string.h> #include<queue> using namespace std; #define MAXM 555555 #define MAXN 2222 struct Edge{ int v,cap,next; }edge[MAXM]; int pre[MAXN]; int cur[MAXN]; int head[MAXN]; int level[MAXN]; int gap[MAXN]; int n,m; int NV,NE; void init(){ NE = 0; memset(head, -1, sizeof(head)); } int SAP(int vs,int vt){ memset(pre,-1,sizeof(pre)); memset(level,0,sizeof(level)); memset(gap,0,sizeof(gap)); for(int i=0;i<=NV;i++)cur[i]=head[i]; int u=pre[vs]=vs,maxflow=0,aug=-1; gap[0]=NV; while(level[vs]<NV){ loop: for(int &i=cur[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(edge[i].cap&&level[u]==level[v]+1){ aug==-1?aug=edge[i].cap:(aug=min(aug,edge[i].cap)); pre[v]=u; u=v; if(v==vt){ maxflow+=aug; for(u=pre[u];v!=vs;v=u,u=pre[u]){ edge[cur[u]].cap-=aug; edge[cur[u]^1].cap+=aug; } aug=-1; } goto loop; } } int minlevel=NV; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(edge[i].cap&&minlevel>level[v]){ cur[u]=i; minlevel=level[v]; } } gap[level[u]]--; if(gap[level[u]]==0)break; level[u]=minlevel+1; gap[level[u]]++; u=pre[u]; } return maxflow; } void addedge(int u,int v,int cap,int cc=0){ //printf("*%d %d %d ", u, v, cap); edge[NE].cap=cap;edge[NE].v=v; edge[NE].next=head[u];head[u]=NE++; edge[NE].cap=cc;edge[NE].v=u; edge[NE].next=head[v];head[v]=NE++; } int main(){ int cas = 1; int n, m; int t; scanf("%d", &t); while(t--){ scanf("%d%d", &n, &m); init(); int T = 0; int sum = 0; for(int i = 1; i <= n; i++){ int p, s, e; scanf("%d%d%d", &p, &s, &e); addedge(0, i, p); for(int t = s; t <= e; t++){ addedge(i, t+n, 1); } T = max(T, e); sum += p; } int src = 0; int sink = n+T+1; for(int i = 1; i <= T; i++){ addedge(i+n, sink, m); } NV = sink+10; ///注意，比一共有的点数加1 printf("Case %d: ", cas++); int ans = SAP(src, sink); //printf("%d ", ans); if(sum == ans) printf("Yes "); else printf("No "); puts(""); } }
最大流dinic模板
#include<iostream> #include<stdio.h> #include<string.h> #include<queue> using namespace std; const int inf = 1000000000; const int maxn = 20000, maxm = 500000; struct Edge{ int v, f, nxt; }; int src, sink; int g[maxn+10]; int nume; Edge e[maxm * 2 +10]; void addedge(int u, int v, int c){ e[++nume].v = v; e[nume].f = c; e[nume].nxt = g[u]; g[u] = nume; e[++nume].v = u; e[nume].f = 0; e[nume].nxt = g[v]; g[v] = nume; } void init(){ memset(g, 0, sizeof(g)); nume = 1; } queue<int> que; bool vis[maxn+10]; int dist[maxn + 10]; void bfs(){ memset(dist, 0, sizeof(dist)); while(!que.empty()) que.pop(); vis[src] = true; que.push(src); while(!que.empty()){ int u = que.front(); que.pop(); for(int i = g[u]; i; i = e[i].nxt) if(e[i].f && !vis[e[i].v]){ que.push(e[i].v); dist[e[i].v] = dist[u] + 1; vis[e[i].v] = true; } } } int dfs(int u, int delta){ if(u == sink){ return delta; }else{ int ret = 0; for(int i = g[u]; delta && i; i = e[i].nxt) if(e[i].f && dist[e[i].v] == dist[u]+1){ int dd = dfs(e[i].v, min(e[i].f, delta)); e[i].f -= dd; e[i^1].f += dd; delta -= dd; ret += dd; } return ret; } } int maxflow(){ int ret = 0; while(true){ memset(vis, 0, sizeof(vis)); bfs(); if(!vis[sink]) return ret; ret += dfs(src, inf); } } int main(){ int n, m; while(scanf("%d%d", &m, &n)!=EOF){ init(); for(int i = 0;i < m; i++){ int u, v, l; scanf("%d%d%d", &u, &v, &l); addedge(u, v, l); } src = 1; sink = n; printf("%d ", maxflow()); } }
线段树区段修改
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; const long long maxa = 100005; long long tree[maxa*4]; long long Mark[maxa*4]; long long mod; void build(long long rt, long long left, long long right){ //printf("%I64d %I64d %I64d====rt, left, right ", rt, left, right); Mark[rt] = 1; if(left == right){ tree[rt] = 1; return; } long long mid = (left + right)/ 2; build(rt*2, left, mid); build(rt*2+1, mid+1, right); } void mark(long long rt, long long left, long long right){ if(left != right){ tree[rt*2] = mull(tree[rt*2], Mark[rt]); tree[rt*2+1] = mull(tree[rt*2+1], Mark[rt]); Mark[rt*2] = mull(Mark[rt*2], Mark[rt]); Mark[rt*2+1] = mull(Mark[rt*2+1], Mark[rt]); Mark[rt] = 1; } } void change(long long rt,long long left, long long right, long long l, long long r, long long mul){ mark(rt, left, right); if(l <= left && right <= r){ tree[rt] = mull(tree[rt], mul); Mark[rt] = mull(Mark[rt], mul); return ; } if(right < l || r < left) return; long long mid = (left + right) / 2; change(rt*2, left, mid, l, r, mul); change(rt*2+1, mid+1, right, l, r, mul); } long long ans[maxa]; void make(long long rt, long long left, long long right){ mark(rt, left, right); if(left == right){ ans[left] = tree[rt]; return; } long long mid = (left + right)/ 2; make(rt*2, left, mid); make(rt*2+1, mid+1, right); } long long a[maxa], b[maxa], c[maxa]; int main(){ long long t; long long n; scanf("%I64d", &t); long long cas = 1; while(t--){ scanf("%I64d%I64d", &n, &mod); for(long long i = 1; i <= n; i++){ scanf("%I64d%I64d", &a[i], &b[i]); c[i] = n; if(a[i] == 2){ c[b[i]] = i-1; } } build(1, 1, n);//printf("*"); for(long long i = 1; i <= n; i++){ if(a[i] == 1){ change(1, 1, n, i, c[i], b[i]); } } make(1, 1, n); printf("Case #%I64d: ", cas++); for(long long i =1;i <= n; i++){ printf("%I64d ", ans[i]); } } }
点到线段距离
double PointToSegDist(double x, double y, double x1, double y1, double x2, double y2) { double cross = (x2 - x1) * (x - x1) + (y2 - y1) * (y - y1); if (cross <= 0) return (x - x1) * (x - x1) + (y - y1) * (y - y1); double d2 = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); if (cross >= d2) return (x - x2) * (x - x2) + (y - y2) * (y - y2); double r = cross / d2; double px = x1 + (x2 - x1) * r; double py = y1 + (y2 - y1) * r; return (x - px) * (x - px) + (y - py) * (y - py); }