6.13 NOI 模拟
\(T1\ first\)
\(bitset\)字符串匹配 \(yyds\)
\(O(\frac{n^2}{w})\)就是正解！
#include
#define MAXN 100005
using namespace std;
int q;
char s[MAXN],y[MAXN],in[MAXN];
bitsetSit[26],Ans;
int main()
{
scanf("%s",s+1);
for(int i=1;s[i];i++)
{
Sit[s[i]-'a'].set(i,1);
}
scanf("%d",&q);
for(int i=1,l,r,x,k,op;i<=q;i++)
{
scanf("%d",&op);
if(op==0)
{
char ch;
scanf("%d %c",&x,&ch);
Sit[s[x]-'a'].set(x,0);
s[x]=ch;
Sit[s[x]-'a'].set(x,1);
}
else
{
Ans.set();
int id=0;
scanf("%d",&k);
for(int j=1;j<=k;j++)
{
scanf("%s",in);
if(in[0]>='0'&&in[0]<='9')
{
int res=0;
for(int j=0;in[j];j++)
{
res=res*10+in[j]-'0';
}
for(int z=1;z<=res;z++) y[++id]='?';
}
else
{
for(int j=0;in[j];j++)
{
y[++id]=in[j];
}
}
}
int len=id;
scanf("%d%d",&l,&r);
for(int j=1;j<=id;j++)
{
if(y[j]=='?') continue;
Ans&=(Sit[y[j]-'a']>>(j-1));
}
printf("%d\n",max(0,(int)((Ans>>l).count()-(Ans>>(r-len+2)).count())));
}
}
}
\(T2\ second\)
最大流\(=\)最小割\(=\)平面图最短路
考虑维护矩阵
\(\begin{bmatrix} S_i & S_i+W_i\\ T_i+W_i & T_i\\ \end{bmatrix}\)
维护加法取\(\min\)矩阵就可以得到区间最大流了
本质上就是把有限的情况组合一下
矩阵乘法\(+\)循环展开食用更佳
#include
#define rs ((now<<1)|1)
#define int long long
#define ls (now<<1)
#define MAXN 500005
using namespace std;
char buf[1<<21],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template
T Read()
{
T x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int (*read)()=Read;
#define read Read
struct Mat
{
int jz[2][2];
void Init()
{
memset(jz,0x3f,sizeof(jz));
}
}zy[MAXN];
struct Seg
{
int l,r;
Mat Sum;
}tr[MAXN<<2];
int A[MAXN],B[MAXN],W[MAXN],n,q;
void build(int now,int l,int r)
{
tr[now].l=l;tr[now].r=r;
if(l==r) return ;
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
Mat mul(Mat a,Mat b)
{
Mat res;
res.Init();
res.jz[0][0]=min({a.jz[0][0]+b.jz[0][0],a.jz[0][1]+b.jz[1][0]});
res.jz[0][1]=min({a.jz[0][0]+b.jz[0][1],a.jz[0][1]+b.jz[1][1]});
res.jz[1][0]=min({a.jz[1][0]+b.jz[0][0],a.jz[1][1]+b.jz[1][0]});
res.jz[1][1]=min({a.jz[1][0]+b.jz[0][1],a.jz[1][1]+b.jz[1][1]});
return res;
}
void upd(int now)
{
tr[now].Sum=mul(tr[ls].Sum,tr[rs].Sum);
}
void change(int now,int poz)
{
if(tr[now].l==poz&&tr[now].r==poz)
{
tr[now].Sum=zy[poz];
return ;
}
int mid=(tr[now].l+tr[now].r)>>1;
if(poz<=mid) change(ls,poz);
else change(rs,poz);
upd(now);
}
Mat res;
Mat query(int now,int l,int r)
{
if(tr[now].l>=l&&tr[now].r<=r)
{
return tr[now].Sum;
}
int mid=(tr[now].l+tr[now].r)>>1;
if(l<=mid&&r>mid) return mul(query(ls,l,r),query(rs,l,r));
else if(l<=mid) return query(ls,l,r);
else if(r>mid) return query(rs,l,r);
}
void upd_poi(int x)
{
zy[x].jz[0][0]=A[x];
zy[x].jz[0][1]=A[x]+W[x];
zy[x].jz[1][0]=B[x]+W[x];
zy[x].jz[1][1]=B[x];
change(1,x);
}
signed main()
{
n=read(),q=read();
for(int i=1;i<=n;i++) A[i]=read();//scanf("%lld",&A[i]);
for(int i=1;i<=n;i++) B[i]=read();//scanf("%lld",&B[i]);
for(int i=1;i \(T3\ third\)
\(DS\) 技不如人
#define Eternal_Battle ZXK
#include
using namespace std;
const int inf=1000000000;
struct edge{
int x,y;
};
struct node{
int l,r,fa,sz,s,v,la;
};
int n,m,k,colsum,x,y,ans,st[100011],tot,hd,idx[100011],edx[100011],edy[100011];
bool fl[100011];
vector vec[100011];
void getring(int a,int fa)
{
tot++;
st[tot]=a;
idx[a]=tot;
for(int i=0;i mp[100011];
void makenode(int a,int c)
{
p[a].sz=1;
p[a].v=c;
p[a].s=c;
}
void link(int a,int b)
{
cnt++;
t[cnt].x=b;
t[cnt].y=h[a];
h[a]=cnt;
}
void downtag(int a,int c)
{
if(!a)return;
p[a].v=p[a].v+c;
p[a].s=p[a].s+c;
p[a].la=p[a].la+c;
}
void down(int a)
{
p[a].fa=0;
downtag(p[a].l,p[a].la);
downtag(p[a].r,p[a].la);
p[a].la=0;
}
void up(int a){
int l=p[a].l,r=p[a].r;
p[l].fa=a;
p[r].fa=a;
p[a].s=min(p[a].v,min(p[l].s,p[r].s));
p[a].sz=p[l].sz+p[r].sz+1;
}
void split(int a,int c,int &l,int &r)
{
if(!a)
{
l=0;
r=0;
return;
}
down(a);
if(p[p[a].l].sz v;
for(int i=h[a];i;i=t[i].y)
{
if(t[i].x==father[a])continue;
father[t[i].x]=a;
int c=dfs(t[i].x);
if(col[a]!=col[t[i].x])downtag(c,1);
v[col[t[i].x]]=merge(v[col[t[i].x]],c);
ban=1;
}
if(ban)
{
for(auto i:v)
{
cnt++;
makenode(cnt,inf);
rt=merge(rt,cnt);
mp[a][i.first]=cnt;
rt=merge(rt,i.second);
cnt++;
makenode(cnt,inf);
rt=merge(rt,cnt);
}
}
else
{
if(!fl[a])
{
makenode(a,0);
rt=a;
}
else
{
rt=0;
}
}
cnt++;
makenode(cnt,inf);
rt=merge(cnt,rt);
f[a]=cnt;
cnt++;
makenode(cnt,inf);
rt=merge(rt,cnt);
return rt;
}
void build()
{
makenode(0,inf);
p[0].sz=0;
cnt=n;
root=dfs(1);
}
void update(int l,int r,int c)
{
int u,v,w;
split(root,r,u,w);
split(u,l-1,u,v);
downtag(v,c);
u=merge(u,v);
root=merge(u,w);
}
void turn(int a,int c)
{
if(mp[a][col[a]])update(getrank(mp[a][col[a]]),getrank(mp[a][col[a]]+1),1);
if(mp[a][c])update(getrank(mp[a][c]),getrank(mp[a][c]+1),-1);
if(a>1)
{
int fa=father[a],u,v,w,val1=getrank(f[a]),val2=getrank(f[a]+1);
split(root,val2,u,w);
split(u,val1-1,u,v);
if(col[father[a]]!=col[a])downtag(v,-1);
if(col[father[a]]!=c)downtag(v,1);
root=merge(u,w);
if(!mp[fa][c])
{
split(root,getrank(f[fa]),u,w);
cnt++;
makenode(cnt,inf);
u=merge(u,cnt);
mp[fa][c]=cnt;
cnt++;
makenode(cnt,inf);
u=merge(u,cnt);
root=merge(u,w);
}
split(root,getrank(mp[fa][c]),u,w);
u=merge(u,v);
root=merge(u,w);
}
col[a]=c;
}
}Ta,Tb;
int main(){
srand(19260817);
scanf("%d%d%d%d",&n,&m,&k,&colsum);
if(n==m)
{
for(int i=1;i<=n;i++)
{
scanf("%d",&Ta.col[i]);
Tb.col[i]=Ta.col[i];
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
edx[i]=x;
edy[i]=y;
vec[x].push_back(y);
vec[y].push_back(x);
}
getring(1,0);
for(int i=1;i<=m;i++)
{
x=edx[i];
y=edy[i];
if(((x!=st[hd])||(y!=st[hd+1]))&&((x!=st[hd+1])||(y!=st[hd])))
{
Ta.link(x,y);
Ta.link(y,x);
}
if(((x!=st[hd])||(y!=st[tot]))&&((x!=st[tot])||(y!=st[hd])))
{
Tb.link(x,y);
Tb.link(y,x);
}
}
for(int i=hd;i<=tot;i++)fl[st[i]]=1;
Ta.build();
Tb.build();
ans=min(Ta.p[Ta.root].s,Tb.p[Tb.root].s);
printf("%d\n",ans);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
Ta.turn(x,y);
Tb.turn(x,y);
ans=min(Ta.p[Ta.root].s,Tb.p[Tb.root].s);
printf("%d\n",ans);
}
}
else
{
for(int i=1;i<=n;i++)scanf("%d",&Ta.col[i]);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
Ta.link(x,y);
Ta.link(y,x);
}
Ta.build();
ans=Ta.p[Ta.root].s;
printf("%d\n",ans);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
Ta.turn(x,y);
ans=Ta.p[Ta.root].s;
printf("%d\n",ans);
}
}
}