闆子集合

圖論

1 #include<bits/stdc++.h>
 2 #define qmin(x,y) (x=min(x,y))
 3 #define qmax(x,y) (x=max(x,y))
 4 #define vi vector<int>
 5 #define vit vector<int>::iterator
 6 #define pir pair<int,int>
 7 #define fr first
 8 #define sc second
 9 #define mp(x,y) make_pair(x,y)
10 #define rsort(x,y) sort(x,y),reverse(x,y)
11 using namespace std;
12 
13 typedef long long ll;
14 const int Maxn=110000;
15 const int inf=0x3f3f3f3f;
16 
17 int to[Maxn],nxt[Maxn],first[Maxn],w[Maxn],tot=1;
18 int dis[Maxn];
19 
20 inline void add(int u,int v,int wi) {
21     to[tot]=v;
22     nxt[tot]=first[u];
23     w[tot]=1;
24     first[u]=tot++;
25 }
26 
27 void dijk(int s) {
28     priority_queue<pir> q;
29     memset(dis,0x3f,sizeof(dis));
30     q.push(mp(dis[s]=0,s));
31     while(!q.empty()) {
32         pir now=q.top();q.pop();
33         if(now.fr!=dis[now.sc]) continue;
34         for(int i=first[now.sc];i;i=nxt[i])
35             if(dis[to[i]]>now.fr+w[i]) {
36                 dis[to[i]]=now.fr+w[i];
37                 q.push(mp(dis[to[i]],to[i]));
38             }
39     }
40 }
41 
42 int main() {
43     return 0;
44 }      

dijkstra

1 #include<bits/stdc++.h>
 2 #define qmin(x,y) (x=min(x,y))
 3 #define qmax(x,y) (x=max(x,y))
 4 #define vi vector<int>
 5 #define vit vector<int>::iterator
 6 #define pir pair<int,int>
 7 #define fr first
 8 #define sc second
 9 #define mp(x,y) make_pair(x,y)
10 #define rsort(x,y) sort(x,y),reverse(x,y)
11 using namespace std;
12 
13 typedef long long ll;
14 const int Maxn=110000;
15 const int inf=0x3f3f3f3f;
16 
17 int to[Maxn],nxt[Maxn],first[Maxn],tot=1;
18 int ran[Maxn],s[Maxn],top,cnt,belong[Maxn],num;
19 
20 inline void add(int u,int v) {
21     to[tot]=v;
22     nxt[tot]=first[u];
23     first[u]=tot++;
24 }
25 
26 int dfs(int root) {
27     int low=ran[root]=++cnt;
28     s[++top]=root;
29     for(int i=first[root];i;i=nxt[i])
30         if(!ran[to[i]]) qmin(low,dfs(to[i]));
31         else if(!belong[to[i]]) qmin(low,ran[to[i]]);
32     if(low==ran[root]) {
33         num++;
34         do belong[s[top]]=num; while(s[top--]!=root) ;
35     }
36     return low;
37 }
38 
39 int main() {
40     return 0;
41 }      

tarjan縮點

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 const int Maxn=110000;
 6 const int inf=0x3f3f3f3f;
 7 
 8 int to[Maxn],nxt[Maxn],first[Maxn],tot=2,w[Maxn];
 9 int s,t,b[Maxn],cur[Maxn];
10 
11 inline void add(int u,int v,int wi) {
12     to[tot]=v;
13     nxt[tot]=first[u];
14     w[tot]=wi;
15     first[u]=tot++;
16     to[tot]=u;
17     nxt[tot]=first[v];
18     w[tot]=wi;
19     first[v]=tot++;
20 }
21 
22 int bfs() {
23     queue<int> q;
24     memset(b,0,sizeof(b));
25     q.push(s);b[s]=1;
26     while(!q.empty()) {
27         int now=q.front();q.pop();
28         for(int i=first[now];i;i=nxt[i])
29             if(w[i]&&!b[to[i]]) {
30                 b[to[i]]=b[now]+1;
31                 q.push(to[i]);
32             }
33     }
34     return b[t];
35 }
36 
37 int dfs(int root,int flow) {
38     if(root==t) return flow;
39     for(int &i=cur[root];i;i=nxt[i])
40         if(w[i]&&b[to[i]]==b[root]+1) {
41             int temp=dfs(to[i],min(w[i],flow));
42             if(temp) {
43                 w[i]-=temp;
44                 w[i^1]+=temp;
45                 return temp;
46             }
47         }
48     return b[root]=0;
49 }
50 
51 int dinic() {
52     int ans=1,temp;
53     while(bfs()) {
54         memcpy(cur,first,sizeof(cur));
55         while(temp=dfs(s,inf)) ans+=temp;
56     }
57     return ans;
58 }
59 
60 int main() {
61     return 0;
62 }      

dinic

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 const int Maxn=110000;
 6 const int inf=0x3f3f3f3f;
 7 
 8 int to[Maxn],nxt[Maxn],first[Maxn],tot=2,w[Maxn],f[Maxn];
 9 int s,t,b[Maxn],vis[Maxn],cost;
10 
11 inline void add(int u,int v,int wi,int fei) {
12     to[tot]=v;
13     nxt[tot]=first[u];
14     w[tot]=wi;
15     f[tot]=fei;
16     first[u]=tot++;
17     to[tot]=u;
18     nxt[tot]=first[v];
19     w[tot]=wi;
20     f[tot]=-fei;
21     first[v]=tot++;
22 }
23 
24 int spfa() {
25     deque<int> q;
26     memset(b,0x3f,sizeof(b));
27     memset(vis,0,sizeof(vis));//!importance
28     q.push_back(t);b[t]=0;
29     while(!q.empty()) {
30         int now=q.front();q.pop_front();
31         for(int i=first[now];i;i=nxt[i])
32             if(w[i^1]&&b[to[i]]>b[now]-f[i]) {
33                 b[to[i]]=b[now]-f[i];
34                 if(!vis[to[i]])
35                     if(q.empty()||b[q.front()]<b[to[i]]) q.push_back(to[i]);
36                     else q.push_front(to[i]);
37                 vis[to[i]]=1;
38             }
39         vis[now]=0;
40     }
41     return b[s]!=inf;
42 }
43 
44 int dfs(int root,int flow) {
45     vis[root]=1;
46     if(root==t) return flow;
47     for(int i=first[root];i;i=nxt[i])
48         if(b[root]==b[to[i]]+f[i]&&!vis[to[i]]&&w[i]) {
49             int temp=dfs(to[i],min(flow,w[i]));
50             if(temp) {
51                 w[i]-=temp;
52                 w[i^1]+=temp;
53                 cost+=f[i]*temp;
54                 return temp;
55             }
56         }
57     return 0;
58 }
59 
60 int mcmf() {
61     int ans=0;
62     while(spfa()) {
63         vis[t]=1;
64         while(vis[t]) {
65             memset(vis,0,sizeof(vis));
66             ans+=dfs(s,inf);
67         }
68     }
69     return ans;
70 }
71 
72 int main() {
73     return 0;
74 }      

zkw費用流

多項式

1 #include<bits/stdc++.h>
 2 #define qmin(x,y) (x=min(x,y))
 3 #define qmax(x,y) (x=max(x,y))
 4 #define vi vector<int>
 5 #define vit vector<int>::iterator
 6 #define pir pair<int,int>
 7 #define fr first
 8 #define sc second
 9 #define mp(x,y) make_pair(x,y)
10 #define rsort(x,y) sort(x,y),reverse(x,y)
11 using namespace std;
12 
13 typedef long long ll;
14 const int Maxn=110000;
15 const int inf=0x3f3f3f3f;
16 const double Pi=acos(-1);
17 
18 struct Complex {
19     double x,y;
20     Complex (double xx=0,double yy=0) {
21         x=xx; y=yy;
22     }
23 };
24 
25 Complex operator + (Complex a,Complex b) {
26     return Complex (a.x+b.x,a.y+b.y);
27 }
28 
29 Complex operator - (Complex a,Complex b) {
30     return Complex (a.x-b.x,a.y-b.y);
31 }
32 
33 Complex operator * (Complex a,Complex b) {
34     return Complex (a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
35 }
36 
37 int limit,l,r[Maxn];
38 
39 void ycl(int x) {
40     limit=1,l=0;
41     while(limit<=x) limit<<=1,l++;
42     for(int i=0;i<limit;i++) r[i]=r[i>>1]>>1|((i&1)<<l-1);
43 }
44 
45 void fft(Complex *a,int type) {
46     for(int i=0;i<limit;i++) if(i<r[i]) swap(a[i],a[r[i]]);
47     for(int mid=1;mid<limit;mid<<=1) {
48         Complex Wn(cos(Pi/mid),type*sin(Pi/mid));
49         for(int j=0;j<limit;j+=mid<<1) {
50             Complex w(1);
51             for(int k=0;k<mid;k++,w=w*Wn) {
52                 Complex x=a[j+k],y=w*a[j+k+mid];
53                 a[j+k]=x+y;
54                 a[j+k+mid]=x-y;
55             }
56         }
57     }
58     if(type==-1) {
59         for(int i=0;i<limit;i++) a[i].x/=limit;
60     }
61 }
62 
63 int main() {
64     return 0;
65 }      

FFT

1 #include<bits/stdc++.h>
 2 #define qmin(x,y) (x=min(x,y))
 3 #define qmax(x,y) (x=max(x,y))
 4 #define vi vector<int>
 5 #define vit vector<int>::iterator
 6 #define pir pair<int,int>
 7 #define fr first
 8 #define sc second
 9 #define mp(x,y) make_pair(x,y)
10 #define rsort(x,y) sort(x,y),reverse(x,y)
11 using namespace std;
12 
13 typedef long long ll;
14 const int Maxn=110000;
15 const int inf=0x3f3f3f3f;
16 const ll mod=998244353;
17 const ll gg=3;
18 const ll gi=332748118;
19 
20 ll powp(ll a,ll b) {
21     ll ans=1;
22     while(b) {
23         if(b&1) ans=ans*a%mod;
24         a=a*a%mod;
25         b>>=1;
26     }
27     return ans;
28 }
29 
30 inline ll modd(ll x) {
31     return x<0?x+mod:x>=mod?x-mod:x;
32 }
33 
34 int limit,l,r[Maxn];
35 
36 void ycl(int x) {
37     limit=1,l=0;
38     while(limit<=x) limit<<=1,l++;
39     for(int i=0;i<limit;i++) r[i]=r[i>>1]>>1|((i&1)<<l-1);
40 }
41 
42 void ntt(ll *a,ll gg) {
43     for(int i=0;i<limit;i++) if(i<r[i]) swap(a[i],a[r[i]]);
44     for(int mid=1;mid<limit;mid<<=1) {
45         ll Wn=powp(gg,(mod-1)/(mid<<1));
46         for(int j=0;j<limit;j+=mid<<1) {
47             ll w=1;
48             while(int k=0;k<mid;k++,w=w*Wn) {
49                 ll x=a[j+k],y=w*a[j+k+mid]%mod;
50                 a[j+k]=modd(x+y);
51                 a[j+k+mid]=modd(x-y);
52             }
53         }
54     }
55     if(gg==gi) {
56         ll inv=powp(limit,mod-2);
57         for(int i=0;i<limit;i++) a[i]=a[i]*inv%mod;
58     }
59 }
60 
61 int main() {
62     return 0;
63 }      

NTT

1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<queue>
  5 #include<cctype>
  6 #define qmin(x,y) (x=min(x,y))
  7 #define qmax(x,y) (x=max(x,y))
  8 #define vi vector<int>
  9 #define vit vector<int>::iterator
 10 #define pir pair<int,int>
 11 #define fr first
 12 #define sc second
 13 #define mp(x,y) make_pair(x,y)
 14 #define rsort(x,y) sort(x,y),reverse(x,y)
 15 using namespace std;
 16 
 17 inline char gc() {
 18 //    static char buf[100000],*p1,*p2;
 19 //    return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
 20     return getchar();
 21 }
 22 
 23 template<class T>
 24 int read(T &ans) {
 25     ans=0;char ch=gc();T f=1;
 26     while(!isdigit(ch)) {
 27         if(ch==EOF) return -1;
 28         if(ch=='-') f=-1;
 29         ch=gc();
 30     }
 31     while(isdigit(ch))
 32         ans=ans*10+ch-'0',ch=gc();
 33     ans*=f;return 1;
 34 }
 35 
 36 template<class T1,class T2>
 37 int read(T1 &a,T2 &b) {
 38     return read(a)!=EOF&&read(b)!=EOF?2:EOF;
 39 }
 40 
 41 template<class T1,class T2,class T3>
 42 int read(T1 &a,T2 &b,T3 &c) {
 43     return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;
 44 }
 45 
 46 typedef long long ll;
 47 const int Maxn=1100000;
 48 const int inf=0x3f3f3f3f;
 49 const ll mod=998244353;
 50 const ll gg=3;
 51 const ll gi=332748118;
 52 
 53 ll powp(ll a,ll b) {
 54     ll ans=1;
 55     while(b) {
 56         if(b&1) ans=ans*a%mod;
 57         a=a*a%mod;
 58         b>>=1;
 59     }
 60     return ans;
 61 }
 62 
 63 ll modd(ll x) {
 64     return x<0?x+mod:x>=mod?x-mod:x;
 65 }
 66 
 67 ll Sqrt(ll a) {
 68     ll x=powp(a,60),e=powp(a,119),k=1,inva=powp(a,mod-2);
 69     while(k<23) {
 70         if(powp(e,1<<23-(k+1))!=1) {
 71             x=x*powp(3,119*(1<<k-1))%mod;
 72             e=inva*x%mod*x%mod;
 73         }
 74         k++;
 75     }
 76     return min(x,mod-x);
 77 }
 78 
 79 int limit,l,r[Maxn];
 80 ll in[Maxn],f[Maxn],n,k,h[Maxn],g[Maxn];
 81 
 82 void ycl(int x) {
 83     limit=1,l=0;
 84     while(limit<=x) limit<<=1,l++;
 85     for(int i=0;i<limit;i++) r[i]=r[i>>1]>>1|((i&1)<<l-1);
 86 }
 87 
 88 void dft(ll *a,ll gg) {
 89     for(int i=0;i<limit;i++) if(i<r[i]) swap(a[i],a[r[i]]);
 90     for(int mid=1;mid<limit;mid<<=1) {
 91         ll Wn=powp(gg,(mod-1)/(mid<<1));
 92         for(int j=0;j<limit;j+=mid<<1) {
 93             ll w=1;
 94             for(int k=0;k<mid;k++,w=w*Wn%mod) {
 95                 ll x=a[j+k],y=a[j+k+mid]*w%mod;
 96                 a[j+k]=modd(x+y);
 97                 a[j+k+mid]=modd(x-y);
 98             }
 99         }
100     }
101     if(gg==gi) {
102         ll inv=powp(limit,mod-2);
103         for(int i=0;i<limit;i++) a[i]=a[i]*inv%mod;
104     }
105 }
106 
107 ll invtmp[Maxn],invtmp2[Maxn];
108 
109 void inv(ll *a,ll *ans,int n) {
110     if(n==1) {
111         ans[0]=powp(a[0],mod-2);
112         return ;
113     }
114     inv(a,ans,n+1>>1);
115     ycl(n<<1);
116     for(int i=0;i<n;i++) invtmp[i]=a[i];
117     for(int i=n;i<limit;i++) invtmp[i]=0;
118     dft(invtmp,gg),dft(ans,gg);
119     for(int i=0;i<limit;i++) ans[i]=ans[i]*modd(2-ans[i]*invtmp[i]%mod)%mod;
120     dft(ans,gi);
121     for(int i=n;i<limit;i++) ans[i]=0;
122 }
123 
124 ll divtmp[Maxn],divtmp2[Maxn];
125 
126 void div(ll *a,ll *b,ll *d,ll *r,int n,int m) {
127     reverse(a,a+n),reverse(b,b+m);
128     inv(b,divtmp,n); ycl(n<<1);
129     for(int i=0;i<limit;i++) divtmp2[i]=a[i];
130     dft(divtmp,gg),dft(divtmp2,gg);
131     for(int i=0;i<limit;i++) d[i]=divtmp[i]*divtmp2[i]%mod;
132     dft(d,gi);
133     for(int i=n-m+1;i<limit;i++) d[i]=0;
134     reverse(d,d+n-m+1);
135     reverse(a,a+n),reverse(b,b+m);
136     for(int i=0;i<=n-m;i++) divtmp[i]=d[i];
137     for(int i=n-m+1;i<limit;i++) divtmp[i]=0;
138     for(int i=0;i<m;i++) divtmp2[i]=b[i];
139     for(int i=m;i<limit;i++) divtmp2[i]=0;
140     dft(divtmp,gg),dft(divtmp2,gg);
141     for(int i=0;i<limit;i++) divtmp[i]=divtmp[i]*divtmp2[i]%mod;
142     dft(divtmp,gi);
143     for(int i=0;i<m-1;i++) r[i]=a[i]-divtmp[i];
144 }//A(x)=B(x)D(x)+R(x):A(x) n,B(x) m,D(x) n-m+1,R(x)<m-1
145 
146 ll stmp[Maxn];
147 
148 void Sqrt(ll *a,ll *ans,int n) {
149     if(n==1) {
150         ans[0]=Sqrt(a[0]);
151         return ;
152     }
153     Sqrt(a,ans,(n+1)>>1);
154     ycl(n<<1);memset(stmp,0,limit<<4);
155     for(int i=0;i<n;i++) ans[i]=ans[i]*2%mod;
156     inv(ans,stmp,n);
157     for(int i=0;i<n;i++) ans[i]=ans[i]*in[2]%mod;
158     ycl(n<<1);
159     dft(ans,gg);
160     for(int i=0;i<limit;i++) ans[i]=ans[i]*ans[i]%mod;
161     dft(ans,gi);
162     for(int i=0;i<n;i++) ans[i]=modd(a[i]+ans[i]);
163     dft(ans,gg),dft(stmp,gg);
164     for(int i=0;i<limit;i++) ans[i]=ans[i]*stmp[i]%mod;
165     dft(ans,gi);
166     for(int i=n;i<limit;i++) ans[i]=0;
167 }
168 
169 void qiudao(ll *a,ll *ans,int n) {
170     for(int i=1;i<n;i++) ans[i-1]=a[i]*i%mod;
171 }
172 
173 void jifen(ll *a,ll *ans,int n) {
174     for(int i=1;i<=n;i++) ans[i]=a[i-1]*in[i]%mod;
175 }
176 
177 ll ltmp[Maxn],ltmp2[Maxn];
178 
179 void ln(ll *a,ll *ans,int n) {
180     ycl(n<<1);memset(ltmp,0,limit<<4);
181     memset(ltmp2,0,limit<<4);
182     inv(a,ltmp,n);
183     qiudao(a,ltmp2,n);
184     ycl(n<<1);
185     dft(ltmp,gg),dft(ltmp2,gg);
186     for(int i=0;i<limit;i++) ltmp[i]=ltmp[i]*ltmp2[i]%mod;
187     dft(ltmp,gi);
188     jifen(ltmp,ans,n-1);
189 }
190 
191 ll etmp[Maxn];
192 
193 void exp(ll *a,ll *ans,int n) {
194     if(n==1) {
195         ans[0]=1;
196         return ;
197     }
198     exp(a,ans,(n+1)>>1);
199     ycl(n<<1);memset(etmp,0,limit<<4);
200     ln(ans,etmp,n);
201     ycl(n<<1);
202     for(int i=0;i<n;i++) etmp[i]=modd(a[i]-etmp[i]);
203     etmp[0]=modd(etmp[0]+1);
204     dft(etmp,gg),dft(ans,gg);
205     for(int i=0;i<limit;i++) ans[i]=ans[i]*etmp[i]%mod;
206     dft(ans,gi);
207     for(int i=n;i<limit;i++) ans[i]=0;
208 }
209 
210 ll ptmp[Maxn];
211 
212 void pow(ll *a,ll *ans,int n,int k) {
213     ln(a,ptmp,n);
214     for(int i=0;i<n;i++) ptmp[i]=ptmp[i]*k%mod;
215     exp(ptmp,ans,n);
216 }
217 
218 signed main() {
219 //    freopen("test.in","r",stdin);
220 //    freopen("out","w",stdout);
221     read(n,k);
222     n++;
223     for(int i=0;i<n;i++) read(f[i]);
224     memcpy(h,f,sizeof(h));
225     in[1]=1;
226     for(int i=2;i<=n;i++) in[i]=modd(-in[mod%i]*(mod/i)%mod);
227     Sqrt(f,g,n);memset(f,0,sizeof(f));
228     inv(g,f,n);memset(g,0,sizeof(g));
229     jifen(f,g,n);memset(f,0,sizeof(f));
230     exp(g,f,n);
231     for(int i=1;i<n;i++) g[i]=modd(h[i]-f[i]);
232     g[0]=modd(2-f[0]);memset(f,0,sizeof(f));
233     ln(g,f,n);
234     f[0]=modd(f[0]+1);memset(g,0,sizeof(g));
235     pow(f,g,n,k);memset(f,0,sizeof(f));
236     qiudao(g,f,n);
237     n--;
238     for(int i=0;i<n;i++) printf("%lld ",f[i]);
239     putchar('\n');
240     return 0;
241 }      

多項式全家桶(loj150)

數論

資料結構

1 #include<bits/stdc++.h>
 2 #define qmin(x,y) (x=min(x,y))
 3 #define qmax(x,y) (x=max(x,y))
 4 #define vi vector<int>
 5 #define vit vector<int>::iterator
 6 #define pir pair<int,int>
 7 #define fr first
 8 #define sc second
 9 #define mp(x,y) make_pair(x,y)
10 #define rsort(x,y) sort(x,y),reverse(x,y)
11 using namespace std;
12 
13 typedef long long ll;
14 const int Maxn=110000;
15 const int inf=0x3f3f3f3f;
16 
17 #define lch ch[root][0]
18 #define rch ch[root][1]
19 #define fat fa[root]
20 
21 int ch[Maxn][2],fa[Maxn];
22 
23 inline int son(int root) {
24     return ch[fat][1]==root;
25 }
26 
27 inline void update(int root) {
28     /*......*/
29 }
30 
31 void rotate(int root) {
32     int y=fat,z=fa[y];
33     if(z) ch[x][son(y)]=root;
34     else rot=root;
35     int d=son(root),x=ch[root][d^1];
36     if(x) fa[x]=y;
37     ch[y][d]=x;
38     ch[x][d^1]=y;
39     fat=z;
40     update(y);
41 }
42 
43 void splay(int root,int topp=0) {
44     while(fat!=topp) {
45         if(fa[fat]!=topp) rotate(son(root)==son(fat)?fat:root);
46         rotate(root);
47     }update(root);
48 }
49 
50 int main() {
51     return 0;
52 }      

Splay

1 #include<bits/stdc++.h>
  2 #define qmin(x,y) (x=min(x,y))
  3 #define qmax(x,y) (x=max(x,y))
  4 #define vi vector<int>
  5 #define vit vector<int>::iterator
  6 #define pir pair<int,int>
  7 #define fr first
  8 #define sc second
  9 #define mp(x,y) make_pair(x,y)
 10 #define rsort(x,y) sort(x,y),reverse(x,y)
 11 using namespace std;
 12 
 13 typedef long long ll;
 14 const int Maxn=110000;
 15 const int inf=0x3f3f3f3f;
 16 
 17 #define lch ch[root][0]
 18 #define rch ch[root][1]
 19 #define fat fa[root]
 20 
 21 int fa[Maxn],ch[Maxn][2],flag[Maxn],st[Maxn],top;
 22 
 23 inline void update(int root) {
 24     /*......*/
 25 }
 26 
 27 inline int isroot(int root) {
 28     return ch[fat][0]==root||ch[fat][1]==root;
 29 }
 30 
 31 inline int son(int root) {
 32     return ch[fat][1]==root;
 33 }
 34 
 35 inline void pushr(int root) {
 36     flag[root]^=1;
 37     swap(lch,rch);
 38 }
 39 
 40 inline void pushdown(int root) {
 41     if(flag[root]) {
 42         flag[root]^=1;
 43         pushr(lch);
 44         pushr(rch);
 45     }
 46 }
 47 
 48 int min(int root) {
 49     pushdown(root);
 50     if(lch) return min(lch);
 51     return root;
 52 }
 53 
 54 void rotate(int root) {
 55     int y=fat,z=fa[y];
 56     if(isroot(z)) ch[z][son(y)]=root;
 57     int d=son(root),x=ch[root][d^1];
 58     ch[y][d]=x;
 59     fa[y]=root;
 60     fa[root]=z;
 61     if(x) fa[x]=y;
 62     ch[root][d^1]=y;
 63     update(y);
 64 }
 65 
 66 void splay(int root) {
 67     top=0;
 68     int temp=root;
 69     while(isroot(temp)) st[++top]=temp,temp=fa[temp];
 70     for(int i=top;i>=1;i--) pushdown(st[i]);
 71     while(isroot(root)) {
 72         if(isroot(fat)) rotate(son(root)==son(fat)?fat:root);
 73         rotate(root);
 74     }update(root);
 75 }
 76 
 77 void access(int root) {
 78     for(int i=0;root;root=fa[i=root])
 79         splay(root),rch=i,update(root);
 80 }
 81 
 82 void makeroot(int root) {
 83     access(root);
 84     splay(root);
 85     pushr(root);
 86 }
 87 
 88 int findroot(int root) {
 89     access(root);
 90     splay(root);
 91     int temp=min(root);
 92     return temp;
 93 }
 94 
 95 void split(int root,int y) {
 96     makeroot(root);
 97     access(y);
 98     splay(y);
 99 }
100 
101 void link(int root,int y) {
102     makeroot(root);
103     if(findroot(y)!=root) fat=y;
104 }
105 
106 void cut(int root,int y) {
107     makeroot(root);
108     if(findroot(y)==root&&fat==y&&rch==0) fat=ch[y][0]=0,update(y);
109 }
110 
111 int main() {
112     return 0;
113 }      

LCT

字元串

1 #include<bits/stdc++.h>
 2 #define qmin(x,y) (x=min(x,y))
 3 #define qmax(x,y) (x=max(x,y))
 4 #define vi vector<int>
 5 #define vit vector<int>::iterator
 6 #define pir pair<int,int>
 7 #define fr first
 8 #define sc second
 9 #define mp(x,y) make_pair(x,y)
10 #define rsort(x,y) sort(x,y),reverse(x,y)
11 using namespace std;
12 
13 typedef long long ll;
14 const int Maxn=110000;
15 const int inf=0x3f3f3f3f;
16 
17 int cmp(int *r,int a,int b,int l) {
18     return r[a]==r[b]&&r[a+l]==r[b+l];
19 }
20 
21 int wa[Maxn],wb[Maxn],ws[Maxn],wv[Maxn];
22 
23 void getsa(int *r,int *sa,int n,int m) {
24     int *x=wa,*y=wb;
25     for(int i=0;i<m;i++) ws[i]=0;
26     for(int i=0;i<n;i++) ws[x[i]=r[i]]++;
27     for(int i=1;i<m;i++) ws[i]+=ws[i-1];
28     for(int i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
29     for(int j=1,p=1;p<n;j<<=1,m=p) {
30         p=0;
31         for(int i=n-j;i<n;i++) y[p++]=i;
32         for(int i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
33         for(int i=0;i<m;i++) ws[i]=0;
34         for(int i=0;i<n;i++) ws[wv[i]=x[y[i]]]++;
35         for(int i=1;i<m;i++) ws[i]+=ws[i-1];
36         for(int i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
37         swap(x,y),p=1,x[sa[0]]=0;
38         for(int i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++;
39     }
40 }
41 
42 void geth(int *r,int *sa,int n) {
43     int k=0;
44     for(int i=0;i<n;i++) ran[sa[i]]=i;
45     for(int i=0;i<n;h[ran[i++]]=k,k=max(0,k-1))
46     for(int j=sa[ran[i]-1];r[i+k]==r[j+k];k++);
47 }
48 
49 int main() {
50     return 0;
51 }      

SA

1 #include<bits/stdc++.h>
 2 #define qmin(x,y) (x=min(x,y))
 3 #define qmax(x,y) (x=max(x,y))
 4 #define vi vector<int>
 5 #define vit vector<int>::iterator
 6 #define pir pair<int,int>
 7 #define fr first
 8 #define sc second
 9 #define mp(x,y) make_pair(x,y)
10 #define rsort(x,y) sort(x,y),reverse(x,y)
11 using namespace std;
12 
13 typedef long long ll;
14 const int Maxn=110000;
15 const int inf=0x3f3f3f3f;
16 
17 int ch[Maxn][26],len[Maxn],link[Maxn],cnt=1;
18 
19 int newnode(int lenn=0) {
20     int now=++cnt;
21     len[now]=lenn;
22 }
23 
24 int cp(int x,int y) {
25     memcpy(ch[x],ch[y],sizeof(ch[x]));
26     link[x]=link[y];
27 }
28 
29 void extend(int x) {
30     int cur=newnode(len[last]+1);
31     int p=last; last=cur;
32     while(p&&!ch[p][x]) {
33         ch[p][x]=cur;
34         p=link[p];
35     }
36     if(p) {
37         int q=ch[p][x];
38         if(len[q]==len[p]+1) link[cur]=q;
39         else {
40             int clone=newnode(len[p]+1);
41             cp(clone,q),link[q]=link[cur]=clone;
42             while(p&&ch[p][x]==q) {
43                 ch[p][x]=clone;
44                 p=link[p];
45             }
46         }
47     }
48     else link[cur]=1;
49 }
50 
51 int main() {
52     return 0;
53 }      

SAM

計算幾何

1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<cmath>
  5 using namespace std;
  6 
  7 struct point {
  8     double x,y;
  9     point (double xx=0,double yy=0) {
 10         x=xx;
 11         y=yy;
 12     }
 13 };
 14 
 15 struct line {
 16     point x,y;
 17     double jj;
 18     line (point xx=point(),point yy=point()) {
 19         x=xx;
 20         y=yy;
 21     }
 22 };
 23 
 24 point operator + (point a,point b) {
 25     return point(a.x+b.x,a.y+b.y);
 26 }
 27 
 28 point operator - (point a,point b) {
 29     return point(a.x-b.x,a.y-b.y);
 30 }
 31 
 32 point operator * (double x,point a) {
 33     return point(x*a.x,x*a.y);
 34 }
 35 
 36 double operator * (point a,point b) {
 37     return a.x*b.y-a.y*b.x;
 38 }
 39 
 40 double operator / (point a,point b) {
 41     return a.x*b.x+a.y*b.y;
 42 }
 43 
 44 bool operator < (line a,line b) {
 45     if(a.jj==b.jj) return dcmp((b.x-a.x)*(b.y-a.x))>=0;
 46     return a.jj<b.jj;
 47 }
 48 
 49 double len(point a) {
 50     return sqrt(a/a);
 51 }
 52 
 53 int dcmp(double x) {
 54     if(fabs(x)<eps) return 0;
 55     return x<0?-1:1;
 56 }
 57 
 58 double dist(point a,line b) {
 59     return fabs((a-b.x)*(b.y-b.x)/len(b.y-b.x));
 60 }
 61 
 62 double dist2(point a,line b) {
 63     if(dcmp((a-b.x)/(b.y-b.x))<0) return len(a-b.x);
 64     if(dcmp((a-b.y)/(b.x-b.y))<0) return len(a-b.y);
 65     return dist(a,b);
 66 }
 67 
 68 bool xj(line a,line b) {
 69     point x=a.y-a.x,y=b.y-b.x;
 70     return dcmp((x*(b.x-a.x))*(x*(b.y-a.x)))<=0&&dcmp((y*(a.x-b.x))*(y*(a.y-b.x)))<=0;
 71 }
 72 
 73 point jd(line a,line b) {
 74     double k1,k2,t;
 75     k1=(b.y-b.x)*(a.y-b.x);
 76     k2=(a.x-b.x)*(b.y-b.x);
 77     t=k1/(k1+k2);
 78     return a.y+t*(a.x-a.y);
 79 }
 80 
 81 int cmp(point x,point y) {
 82     int k=dcmp((x-p[1])*(y-p[1]));
 83     if(k==0) return x.x<y.x;
 84     return k>0;
 85 }
 86 
 87 void tb() {
 88     int k=1;
 89     for(int i=1;i<=n;i++)
 90         if(p[i].y<p[k].y||(p[i].y==p[k].y&&p[i].x<p[k].x)) k=i;
 91     swap(p[1],p[k]);
 92     sort(p+2,p+n+1,cmp);
 93     num=1;
 94     sxz[1]=p[1];
 95     p[++n]=p[1];
 96     for(int i=2;i<=n;i++) {
 97         while(num!=1&&dcmp((sxz[num]-sxz[num-1])*(p[i]-sxz[num-1]))<=0) num--;
 98         sxz[++num]=p[i];
 99     }
100 }
101 
102 void bpm() {
103     sort(l+1,l+n+1);
104     int top=2,bot=1;
105     for(int i=1;i<=n;i++) {
106         if(dcmp(l[i].jj-l[i-1].jj)!=0) tot++;
107         l[tot]=l[i];
108     }
109     n=tot;q[1]=l[1];q[2]=l[2];
110     for(int i=3;i<=n;i++) {
111         while(bot<top&&jud(q[top],q[top-1],l[i])) top--;
112         while(bot<top&&jud(q[bot],q[bot+1],l[i])) bot++;
113         q[++top]=l[i];
114     }
115     while(bot<top&&jud(q[top],q[top-1],q[bot])) top--;
116     while(bot<top&&jud(q[bot],q[bot+1],q[top])) bot++;
117     q[top+1]=q[bot];
118     tot=0;
119     for(int i=bot;i<=top;i++) sxz[++tot]=jd(q[i],q[i+1]);
120 }
121 
122 int main() {
123     return 0;
124 }      

計算幾何

轉載于:https://www.cnblogs.com/shanxieng/p/my_banzis.html