当前位置：网站首页>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;
}
边栏推荐
- 2022/7/11 exam summary
- Strtus2历史漏洞复现
- Summary of distributed related interview questions
- "Door lock" ignites a heated discussion on the safety of living alone. The new poster picture is suffocating
- Crawler - > tpimgspider
- Summary of traversal methods of list, set, map, queue, deque and stack
- If the thread crashes, why doesn't it cause the JVM to crash? What about the main thread?
- PHP environment deployment
- Establishment and use of openstack cloud platform
- What are the differences between FileInputStream and bufferedinputstream?
猜你喜欢
Rack server expansion memory
Burp suite Chapter 4 advanced options for SSL and proxy
A tutorial for mastering MySQL database audit characteristics, implementation scheme and audit plug-in deployment
Burp Suite-第三章 如何使用Burp Suite代理
R language foundation
Database foundation
Software engineering -- dental clinic -- demand acquisition
AQS implementation principle
Burp Suite-第八章 如何使用Burp Intruder
【 fastjson1.2.24反序列化漏洞原理代码分析】
随机推荐
Master slave database deployment
es6中函数默认参数、箭头函数、剩余参数-讲解
2022.7.22DAY612
The difference between overloading and rewriting
《门锁》引爆独居安全热议 全新海报画面令人窒息
shardingjdbc踩坑记录
Rewriting and overloading
小组成员参加2022中国多媒体大会
Understand microservices bit by bit
【 fastjson1.2.24反序列化漏洞原理代码分析】
Burp Suite-第八章 如何使用Burp Intruder
2022/7/9 exam summary
FTP service
PHP environment deployment
BGP的基本配置
API (common class 2)
No valid host was found when setting up openstack to create an instance There are not enough hosts available. code:500
2022/7/7 exam summary
The difference between equals() and = =
[xshell7 free download and installation]