当前位置：网站首页>Template summary
Template summary
2022-07-26 08:07:00 【Misty rain】
Chairman tree
int Insert(int last,int l,int r,int x)
{
int k=++tot;
lson[k]=lson[last];
rson[k]=rson[last];
sum[k]=sum[last]+1;
if(l==r) return k;
int mid=(l+r)>>1;
if(x<=mid) lson[k]=Insert(lson[k],l,mid,x);
else rson[k]=Insert(rson[k],mid+1,r,x);
pushup(k);
return k;
}
Line tree merge
int Merge(int x,int y,int l,int r)
{
if(!x||!y) return x+y;
if(l==r)
{
Max[x]=max(Max[x],Max[y]);
sum[x]+=sum[y];
return x;
}
int mid=(l+r)>>1;
lson[x]=Merge(lson[x],lson[y],l,mid);
rson[x]=Merge(rson[x],rson[y],mid+1,r);
pushup(x);
return x;
}
``` Be persistent 0/1trie
```cpp
void Insert(int x,LL val,int len,int id,int y)
{
if(len<0)
{
Max[x]=id;
return;
}
int c=((val>>len)&1);
if(y) tr[x][c^1]=tr[y][c^1];
tr[x][c]=++tot;
Insert(tr[x][c],val,len-1,id,tr[y][c]);
Max[x]=max(Max[tr[x][0]],Max[tr[x][1]]);
}
int Query(int x,LL val,int len,int l,int r)
{
if(len<0) return Max[x];
int c=((val>>len)&1);
if(Max[tr[x][c^1]]>=l) return Query(tr[x][c^1],val,len-1,l,r);
else return Query(tr[x][c],val,len-1,l,r);
}
Persistent arrays
struct Array
{
int lson[N*25],rson[N*25],val[N*25];
int rot[25*N],tot;
Array()
{
tot=0;
memset(rot,0,sizeof(rot));
memset(lson,0,sizeof(lson));
memset(rson,0,sizeof(rson));
memset(val,0,sizeof(val));
}
int build(int k,int l,int r)
{
k=++tot;
if(l==r)
{
val[k]=A[l];
return k;
}
int mid=(l+r)>>1;
lson[k]=build(lson[k],l,mid);
rson[k]=build(rson[k],mid+1,r);
return k;
}
int Modify(int last,int l,int r,int x,int v)
{
int k=++tot;
lson[k]=lson[last];
rson[k]=rson[last];
if(l==r)
{
val[k]=v;
return k;
}
int mid=(l+r)>>1;
if(x<=mid) lson[k]=Modify(lson[last],l,mid,x,v);
else rson[k]=Modify(rson[last],mid+1,r,x,v);
return k;
}
int Query(int k,int l,int r,int x)
{
if(l==r) return val[k];
int mid=(l+r)>>1;
if(x<=mid) return Query(lson[k],l,mid,x);
return Query(rson[k],mid+1,r,x);
}
void Copy(int a,int b)
{
rot[a]=rot[b];
}
void Update(int a,int b,int x,int v)
{
rot[a]=Modify(rot[b],1,n,x,v);
}
int Ask(int a,int x)
{
return Query(rot[a],1,n,x);
}
}
Decision monotonicity dichotomous queue
LL calc(LL l,LL r)
{
LL mid=(l+r)>>1;
return s[r]-s[mid]-1ll*(r-mid)*a[mid]+a[mid]*(mid-l+1)-(s[mid]-s[l-1]);
}
LL pre[N];
bool Better(int x,int a,int b)
{
if(f[a]+calc(a+1,x)==f[b]+calc(b+1,x)) return pre[a]<pre[b];
return f[a]+calc(a+1,x)<f[b]+calc(b+1,x);
}
LL check(LL cost)
{
LL l=1,r=0;
q[++r]=Node(1,n,0);
for(LL i=1;i<=n;i++)
{
while(l<=r&&q[l].r==i-1) l++;
LL j=q[l].pos;
q[l].l=i;
f[i]=f[j]+calc(j+1,i)-cost;
pre[i]=pre[j]+1;
int x=n+1;
while(l<=r&&Better(q[r].l,i,q[r].pos)) x=q[r].l,r--;
if(l>r)
{
q[++r]=Node(i+1,n,i);
continue;
}
if(Better(q[r].r,q[r].pos,i)&&x+1<=n)
{
q[++r]=Node(x,n,i);
continue;
}
LL L=q[r].l,R=q[r].r,pos=q[r].pos,mid;
while(L<=R)
{
mid=(L+R)>>1;
if(Better(mid,i,pos))
{
x=mid;
R=mid-1;
}
else L=mid+1;
}
q[r].r=x-1;
q[++r]=Node(x,n,i);
}
return pre[n];
}
wqs Two points
LL ans,l=-5e11,r=5e11,mid;
while(l<=r)
{
mid=l+r>>1;
if(check(mid)<=m) l=mid+1,ans=mid;
else r=mid-1;
}
check(ans);
printf("%lld\n",1ll*f[n]+ans*m);
treap
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
const int INF =1e8;
struct node
{
int l,r;
int key,val;
int cnt,size;
}tr[N];
int root,tot=0;
int New(int key)
{
++tot;
tr[tot].l=tr[tot].r=0;
tr[tot].key=key;
tr[tot].val=rand();
tr[tot].cnt=tr[tot].size=1;
return tot;
}
void pushup(int x)
{
tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size+tr[x].cnt;
}
void zig(int &x)
{
int y=tr[x].l;
tr[x].l=tr[y].r;
tr[y].r=x;
x=y;
pushup(tr[x].r);
pushup(x);
}
void zag(int &x)
{
int y=tr[x].r;
tr[x].r=tr[y].l;
tr[y].l=x;
x=y;
pushup(tr[x].l);
pushup(x);
}
void Insert(int &x,int key)
{
if(!x)
{
x=New(key);
return;
}
if(tr[x].key==key) tr[x].cnt++;
else if(tr[x].key<key)
{
Insert(tr[x].r,key);
if(tr[tr[x].r].val>tr[x].val) zag(x);
}
else
{
Insert(tr[x].l,key);
if(tr[tr[x].l].val>tr[x].val) zig(x);
}
pushup(x);
}
void Remove(int &x,int key)
{
if(!x) return;
if(tr[x].key==key)
{
if(tr[x].cnt>1) tr[x].cnt--;
else if(tr[x].l||tr[x].r)
{
if(!tr[x].r||tr[tr[x].l].val>tr[tr[x].r].val)
{
zig(x);
Remove(tr[x].r,key);
}
else
{
zag(x);
Remove(tr[x].l,key);
}
}
else x=0;
}
else if(tr[x].key<key) Remove(tr[x].r,key);
else Remove(tr[x].l,key);
pushup(x);
}
int Rank(int x,int key)
{
if(!x) return 0;
if(tr[x].key==key) return tr[tr[x].l].size+1;
else if(tr[x].key<key) return tr[tr[x].l].size+tr[x].cnt+Rank(tr[x].r,key);
else return Rank(tr[x].l,key);
}
int Kth(int x,int rk)
{
if(!x) return INF;
if(tr[tr[x].l].size>=rk) return Kth(tr[x].l,rk);
else if(tr[tr[x].l].size+tr[x].cnt>=rk) return tr[x].key;
else return Kth(tr[x].r,rk-tr[tr[x].l].size-tr[x].cnt);
}
int Pre(int x,int val)
{
if(!x) return -INF;
if(tr[x].key>=val) return Pre(tr[x].l,val);
else return max(tr[x].key,Pre(tr[x].r,val));
}
int Next(int x,int val)
{
if(!x) return INF;
if(tr[x].key<=val) return Next(tr[x].r,val);
else return min(tr[x].key,Next(tr[x].l,val));
}
int main()
{
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
srand(time(0));
int n;
cin>>n;
New(-INF);
New(INF);
root=1;
tr[1].r=2;
pushup(1);
while(n--)
{
int opt,x;
scanf("%d %d",&opt,&x);
if(opt==1) Insert(root,x);
else if(opt==2) Remove(root,x);
else if(opt==3) printf("%d\n",Rank(root,x)-1);
else if(opt==4) printf("%d\n",Kth(root,x+1));
else if(opt==5) printf("%d\n",Pre(root,x));
else printf("%d\n",Next(root,x));
}
return 0;
}
fhq_treap
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e8;
const int N = 1e5+7;
struct node
{
int l,r;
int val,key;
int cnt,size;
}tr[N];
int root,tot=0;
int New(int key)
{
tot++;
tr[tot].l=tr[tot].r=0;
tr[tot].key=key;
tr[tot].val=rand();
tr[tot].cnt=tr[tot].size=1;
return tot;
}
void pushup(int x)
{
tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size+tr[x].cnt;
}
void Split(int k,int key,int &x,int &y)
{
if(!k)
{
x=y=0;
return;
}
if(tr[k].key<=key)
{
x=k;
Split(tr[k].r,key,tr[k].r,y);
}
else
{
y=k;
Split(tr[k].l,key,x,tr[k].l);
}
pushup(k);
}
void Divide(int k,int rk,int &x,int &y)
{
if(!k)
{
x=y=0;
return;
}
if(tr[tr[k].l].size+1<=rk)
{
x=k;
Divide(tr[k].r,rk-tr[tr[k].l].size-1,tr[k].r,y);
}
else
{
y=k;
Divide(tr[k].l,rk,x,tr[k].l);
}
pushup(k);
}
int Merge(int x,int y)
{
if(!x||!y) return x+y;
if(tr[x].val>tr[y].val)
{
tr[x].r=Merge(tr[x].r,y);
pushup(x);
return x;
}
else
{
tr[y].l=Merge(x,tr[y].l);
pushup(y);
return y;
}
}
void Insert(int key)
{
int x,y,z;
Split(root,key,x,y);
z=New(key);
root=Merge(Merge(x,z),y);
}
void Remove(int key)
{
int A,B,x,y;
Split(root,key,A,B);
Split(A,key-1,x,y);
if(y) y=Merge(tr[y].l,tr[y].r);
root=Merge(Merge(x,y),B);
}
int Rank(int key)
{
int A,B;
Split(root,key-1,A,B);
int res=tr[A].size;
root=Merge(A,B);
return res+1;
}
int Kth(int rk)
{
int A,B,x,y;
Divide(root,rk,A,B);
Divide(A,rk-1,x,y);
int res=tr[y].key;
root=Merge(Merge(x,y),B);
return res;
}
int Pre(int key)
{
int A,B,x,y;
Split(root,key-1,A,B);
Divide(A,tr[A].size-1,x,y);
int res=tr[y].key;
root=Merge(Merge(x,y),B);
return res;
}
int Next(int key)
{
int A,B,x,y;
Split(root,key,A,B);
Divide(B,1,x,y);
int res=tr[x].key;
root=Merge(A,Merge(x,y));
return res;
}
int main()
{
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
srand(time(0));
New(-INF);
New(INF);
root=Merge(1,2);
int n;
cin>>n;
while(n--)
{
int opt,x;
scanf("%d %d",&opt,&x);
if(opt==1) Insert(x);
else if(opt==2) Remove(x);
else if(opt==3) printf("%d\n",Rank(x)-1);
else if(opt==4) printf("%d\n",Kth(x+1));
else if(opt==5) printf("%d\n",Pre(x));
else printf("%d\n",Next(x));
}
return 0;
}
splay
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
const int INF = 1e9;
struct node
{
int l,r,fa;
int size,cnt;
int key;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define siz(x) tr[x].size
#define cnt(x) tr[x].cnt
#define key(x) tr[x].key
#define fa(x) tr[x].fa
}tr[N];
int root,tot=0;
int New(int key)
{
++tot;
l(tot)=r(tot)=fa(tot)=0;
cnt(tot)=siz(tot)=1;
key(tot)=key;
return tot;
}
void pushup(int x)
{
siz(x)=siz(l(x))+siz(r(x))+cnt(x);
}
void put()
{
cout<<"---------------"<<endl;
cout<<root<<endl;
for(int i=1;i<=tot;i++)
cout<<i<<' '<<key(i)<<' '<<l(i)<<' '<<r(i)<<endl;
cout<<"---------------"<<endl;
}
void rotate(int x)
{
int y=fa(x),z=fa(y);
if(l(z)==y) l(z)=x;
else r(z)=x;
fa(x)=z;
if(l(y)==x)
{
l(y)=r(x);
fa(r(x))=y;
r(x)=y;
}
else
{
r(y)=l(x);
fa(l(x))=y;
l(x)=y;
}
fa(y)=x;
pushup(y);
pushup(x);
}
void splay(int x,int k)
{
while(fa(x)!=k)
{
int y=fa(x),z=fa(y);
if(z!=k)
{
if((r(z)==y)!=(r(y)==x)) rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k) root=x;
}
void Insert(int key)
{
int x=root,pre=0;
while(x)
{
if(key(x)==key)
{
cnt(x)++;
break;
}
pre=x;
if(key(x)<key) x=r(x);
else x=l(x);
}
if(!x)
{
x=New(key);
fa(x)=pre;
if(pre)
{
if(key(x)<key(pre)) l(pre)=x;
else r(pre)=x;
}
}
splay(x,0);
}
void Find(int key)
{
int x=root;
if(!x) return;
while(key(x)!=key)
{
if(l(x)&&key(x)>key) x=l(x);
else if(r(x)&&key(x)<key) x=r(x);
else break;
}
splay(x,0);
}
int Pre(int key)
{
Find(key);
int x=l(root);
while(r(x)) x=r(x);
return x;
}
int Next(int key)
{
Find(key);
int x=r(root);
while(l(x)) x=l(x);
return x;
}
void Del(int key)
{
int a=Pre(key);
int b=Next(key);
splay(a,0);
splay(b,a);
int x=l(b);
if(cnt(x)>1) cnt(x)--,splay(x,0);
else l(b)=0;
}
int Kth(int k)
{
int x=root;
while(1)
{
if(k<=siz(l(x))) x=l(x);
else if(k<=siz(l(x))+cnt(x)) return x;
else
{
k-=(siz(l(x))+cnt(x));
x=r(x);
}
}
}
int n;
int main()
{
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
cin>>n;
Insert(-INF);
Insert(INF);
while(n--)
{
int opt,x;
scanf("%d %d",&opt,&x);
if(opt==1) Insert(x);
else if(opt==2) Del(x);
else if(opt==3)
{
Find(x);
printf("%d\n",siz(l(root)));
}
else if(opt==4) printf("%d\n",key(Kth(x+1)));
else if(opt==5)
{
Insert(x);
printf("%d\n",key(Pre(x)));
Del(x);
}
else
{
Insert(x);
printf("%d\n",key(Next(x)));
Del(x);
}
}
return 0;
}
link_cut_tree
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 3e5+7;
struct node
{
LL s[2];
LL fa;
LL v,sum;
LL tag;
#define tag(x) tr[x].tag
#define l(x) tr[x].s[0]
#define r(x) tr[x].s[1]
#define fa(x) tr[x].fa
#define val(x) tr[x].v
#define sum(x) tr[x].sum
}tr[N];
void Reverse(LL x)
{
swap(l(x),r(x));
tag(x)^=1;
}
void pushup(LL x)
{
sum(x)=sum(l(x))^sum(r(x))^val(x);
}
void pushdown(LL x)
{
if(tag(x))
{
tag(x)=0;
Reverse(l(x));
Reverse(r(x));
}
}
bool isroot(LL x)
{
if(l(fa(x))!=x&&r(fa(x))!=x) return 1;
return 0;
}
LL n;
void rotate(LL x)
{
LL y=fa(x),z=fa(y);
LL a=(r(y)==x),b=(r(z)==y);
if(!isroot(y)) tr[z].s[b]=x;
fa(x)=z;
tr[y].s[a]=tr[x].s[a^1];fa(tr[x].s[a^1])=y;
tr[x].s[a^1]=y;fa(y)=x;
pushup(y);
pushup(x);
}
LL stk[N];
void spread(LL x)
{
LL tot=0;
stk[++tot]=x;
while(!isroot(x))
{
x=fa(x);
stk[++tot]=x;
}
while(tot)
{
pushdown(stk[tot]);
tot--;
}
}
void splay(LL x)
{
spread(x);
while(!isroot(x))
{
LL y=fa(x),z=fa(y);
if(!isroot(y))
{
if((r(z)==y)!=(r(y)==x)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(LL x)
{
LL y=0,r=x;
for(;x;x=fa(x))
{
splay(x);
r(x)=y;
y=x;
pushup(x);
}
splay(r);
}
void makeroot(LL x)
{
access(x);
Reverse(x);
}
LL findroot(LL x)
{
access(x);
while(l(x))
{
pushdown(x);
x=l(x);
}
splay(x);
return x;
}
void split(LL x,LL y)
{
makeroot(x);
access(y);
}
void link(LL x,LL y)
{
makeroot(x);
if(findroot(y)!=x) fa(x)=y;
}
void cut(LL x,LL y)
{
makeroot(x);
if(findroot(y)==x&&fa(y)==x&&l(y)==0)
{
r(x)=fa(y)=0;
pushup(x);
}
}
LL m;
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
cin>>n>>m;
for(LL i=1;i<=n;i++) scanf("%lld",&val(i));
while(m--)
{
LL opt,x,y;
scanf("%lld %lld %lld",&opt,&x,&y);
if(opt==0)
{
split(x,y);
printf("%lld\n",tr[y].sum);
}
else if(opt==1) link(x,y);
else if(opt==2) cut(x,y);
else
{
splay(x);
val(x)=y;
pushup(x);
}
}
return 0;
}
dinic
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1200,M=1e6+7;
const int INF = 1e18+7;
struct node
{
int y,next;
}e[M];
int link[N],t=1;
int n,m;
int f[M];
void add(int x,int y,int v)
{
e[++t].y=y;
e[t].next=link[x];
f[t]=v;
link[x]=t;
}
int d[N],cur[N];
queue<int> q;
int S,T;
int Extend()
{
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++) d[i]=-1;
q.push(S);
d[S]=0;
cur[S]=link[S];
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(d[y]==-1&&f[i])
{
d[y]=d[x]+1;
cur[y]=link[y];
if(y==T) return 1;
q.push(y);
}
}
}
return 0;
}
int Find(int x,int limit)
{
if(x==T) return limit;
int flow=0;
for(int i=cur[x];i&&flow<limit;i=e[i].next)
{
cur[x]=i;
int y=e[i].y;
if(d[y]==d[x]+1&&f[i])
{
int val=Find(y,min(f[i],limit-flow));
if(!val) d[y]=-1;
f[i]-=val;
f[i^1]+=val;
flow+=val;
}
}
return flow;
}
int dinic()
{
int ans=0,flow=0;
while(Extend())
{
while(flow=Find(S,INF))
{
ans+=flow;
}
}
return ans;
}
signed main()
{
freopen("ff.in","r",stdin);
freopen("ff.out","w",stdout);
cin>>n>>m>>S>>T;
for(int i=1;i<=m;i++)
{
int x,y,v;
scanf("%lld %lld %lld",&x,&y,&v);
add(x,y,v);
add(y,x,0);
}
printf("%lld",dinic());
return 0;
}
边栏推荐
- Introduction to C language (8)
- How to close the high-level port
- CentOS install mysql5.7
- NFS service and Samba service deployment
- JSP action -- usebean action
- Summary of traversal methods of list, set, map, queue, deque and stack
- The bigger the project is, the bigger it is. This is how I split it
- JSP built-in object (implicit object)
- 99 multiplication table and inverted triangle 99 multiplication table
- Common database commands (special for review)
猜你喜欢
How to close the high-level port
99 multiplication table and inverted triangle 99 multiplication table
万字长文 | 深入理解 OpenFeign 的架构原理
Burp suite Chapter 3 how to use burp suite agent
Table fix specific rows
Software engineering -- dental clinic -- demand analysis
Summarize the common high-frequency interview questions of the software testing post
Establishment and use of openstack cloud platform
Logical volume management (LVM)
File parsing (JSON parsing)
随机推荐
Brief description of hystrix configuration
一键部署LAＭP和LNMP架构
这是一张图片
Use of JMeter performance test to store response content to file listener
Use js to count the number of occurrences of each string in the string array, and format it into an object array.
Burp Suite-第五章 如何使用Burp Target
万字长文 | 深入理解 OpenFeign 的架构原理
一点一点理解微服务
Burp suite Chapter 5 how to use burp target
Utils connection pool
Lnmp+wordpress to quickly build a personal website
Common methods of string: construction method, other methods
JSP action -- usebean action
2W word detailed data Lake: concept, characteristics, architecture and cases
Summary of API method
utils 连接池
Implementation class under map interface
Stack simulation queue
Burp suite Chapter 7 how to use burp scanner
JMeter performance test saves the results of each interface request to a file