模拟赛
。。。
T1 绿绿和串串
学习 manacher。
先说求回文串，manacher 算法，每次记录向右能延伸最长的回文串和回文中心。
这样对于新扩展的字符，按已有的回文中心对称过去，会得到一个已经求出的回文长度，在这个基础上向两端扩展就好了。
对于普通的回文串，有奇回文和偶回文两种，为了方便计算，我们通常在每两个字符之间插入无用字符，这样就可以都按奇回文来算了，注意长度也要有变化。
回到这道题，很容易发现我们要找出前缀回文串或者后缀回文串（前缀时要判一下右端点）的回文中心，并且都是奇回文，所以直接上 马拉车。
为了方便，代码实现中反转了字符串，注意最后输出答案要翻回来。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 5e6+5;
int t,n;
char s[N];
int vs[N];
int p[N];
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%d",&t);
while(t--)
{
scanf("%s",s+1); n=strlen(s+1);
if(n==1) {printf("1\n"); continue;}
for(int i=0;i<=n+1;i++) vs[i]=p[i]=0;
s[0]='&'; s[n+1]='*';
reverse(s+1,s+1+n); p[1]=1;
for(int i=1,r=0,mid=0;i<=n;i++)
{
if(i<=r) p[i]=min(p[2*mid-i],r-i+1);
while(s[i+p[i]]==s[i-p[i]]) p[i]++;
if(i+p[i]-1>r) mid=i,r=i+p[i]-1;
if(i-p[i]+1==1) vs[i]=1;
else if(i+p[i]-1==n&&vs[i-p[i]+1]) vs[i]=1;
}
for(int i=1;i<=n;i++) if(vs[n-i+1]) printf("%d ",i);
putchar('\n');
}
return 0;
}
T2
思维题（发现没有大样例）。
首先特判不用动的情况。
只需要考虑收尾两个位置，假如第一个数不是最大值，那么动一下它，后面的都会排好，这时候再动一下最后一个（一定已经是最大值了）就好了。
也可以选择动最后一个数，前提是第一个数不是最大值或最后一个数不是最小值。这时候只需要两次。
如果恰好第一个数就是最大值并且最后一个数就是最小值呢？这时候任意动一次中间的数就和上述情况一样了。需要 \(3\) 次。
另外，还有可能就是恰好有一个位置能一次解决，特判一下就好。（赛事唐氏 BIT，其实可以直接记录最大值）
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int t;
int n,a[N];
void work()
{
int mx=0;
bool fl=1;
for(int i=1;i<=n;i++) fl&=(a[i]==i);
if(fl) return printf("0\n"),void(0);
for(int i=1;i<=n;i++)
{
mx=max(mx,a[i]);
if(a[i]==i&&mx==i) return printf("1\n"),void(0);
}
if(a[1]!=n||a[n]!=1) return printf("2\n"),void(0);
return printf("3\n"),void(0);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
work();
}
return 0;
}
T3 一个古老的序列
链接就是题解，讲的很清晰。
学习新知识，线段树维护历史版本和！！！。
我们要求询问区间所有子区间的 \(min \times max\)，当然考虑每一个数作为最大值或最小值的管辖范围。
先考虑只求一个区间的 \(min \times max\)，可以直接单调栈维护：枚举右端点，确定每一个点作为最大值或最小值的管辖范围，然后线段树维护对于每一个左端点，当前右端点对应答案。
但是我们发现上述想法只能求出一个区间的答案，而不是所有子区间的答案和。
如果想同时处理所有子区间，其实就是对于每一个左端点，要维护左端点到右端点每一个时刻的答案和。这都是我们之前计算过的，所以考虑怎么维护历史版本和。
有一个很巧妙的引入是矩阵乘法！。用一维存当前值，另一维存历史版本和。
我们设计一个转移矩阵来将当前答案统计到历史和里:
\[\begin{bmatrix} a & b \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} a & a+b \end{bmatrix} \]这样写相当方便啊，每次更新完乘一次转移矩阵就好了，其他操作完全没有变化。
可能会比不用矩阵直接转移慢一点，但是写法更简单。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5,mod = 1e9+7;
int n,m,a[N],ans[N];
struct Q {int l,id;}; vector<Q> q[N];
int qx[N<<1],qi[N<<1],lx,li;
struct M
{
int a[2][2];
bool jd()
{
return a[0][0]==1&&a[1][1]==1&&a[0][1]==0&&a[1][0]==0;
}
M () {memset(a,0,sizeof(a));}
void rs() {a[0][1]=a[1][0]=0; a[0][0]=a[1][1]=1;}
M operator * (const M &x) const
{
M c;
for(int i=0;i<2;i++)
for(int k=0;k<2;k++)
for(int j=0;j<2;j++)
c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*x.a[k][j])%mod;
return c;
}
};
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod; b>>=1;
}
return res;
}
M con(int c)
{
M res; res.a[0][0]=c; res.a[1][1]=1;
return res;
}
namespace SEG
{
struct T {int l,r; M sum,lz;} tr[N<<2];
inline void pushup(int k)
{
tr[k].sum.a[0][0]=(1ll*tr[k<<1].sum.a[0][0]+tr[k<<1|1].sum.a[0][0])%mod;
tr[k].sum.a[0][1]=(1ll*tr[k<<1].sum.a[0][1]+tr[k<<1|1].sum.a[0][1])%mod;
}
void bui(int k,int l,int r)
{
tr[k].lz.rs(); tr[k].sum.a[0][0]=r-l+1;
tr[k].l=l; tr[k].r=r;
if(l==r) return;
int mid=l+r>>1;
bui(k<<1,l,mid); bui(k<<1|1,mid+1,r);
}
void down(int k)
{
if(tr[k].lz.jd()) return;
tr[k<<1].sum=tr[k<<1].sum*tr[k].lz;
tr[k<<1].lz=tr[k<<1].lz*tr[k].lz;
tr[k<<1|1].sum=tr[k<<1|1].sum*tr[k].lz;
tr[k<<1|1].lz=tr[k<<1|1].lz*tr[k].lz;
tr[k].lz.rs();
}
void add(int k,int l,int r,M c)
{
if(l<=tr[k].l&&tr[k].r<=r)
{
tr[k].sum=tr[k].sum*c; tr[k].lz=tr[k].lz*c; return;
}
down(k);
int mid=tr[k].l+tr[k].r>>1;
if(l<=mid) add(k<<1,l,r,c);
if(r>mid) add(k<<1|1,l,r,c);
pushup(k);
}
int que(int k,int l,int r)
{
if(tr[k].l>=l&&tr[k].r<=r) return tr[k].sum.a[0][1];
down(k);
int mid=tr[k].l+tr[k].r>>1,res=0;
if(l<=mid) res=que(k<<1,l,r);
if(r>mid) res=(res+1ll*que(k<<1|1,l,r))%mod;
return res;
}
}; using namespace SEG;
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
bui(1,1,n);
for(int i=1;i<=m;i++)
{
int l,r; scanf("%d%d",&l,&r);
q[r].push_back({l,i});
}
lx=li=0; M I; I.rs(); I.a[0][1]=1;
for(int i=1;i<=n;i++)
{
while(lx&&a[qx[lx]]<a[i])
{
int c=qpow(a[qx[lx]],mod-2);
add(1,qx[lx-1]+1,qx[lx],con(c));
lx--;
}
while(li&&a[qi[li]]>a[i])
{
int c=qpow(a[qi[li]],mod-2);
add(1,qi[li-1]+1,qi[li],con(c));
li--;
}
add(1,qx[lx]+1,i,con(a[i]));
add(1,qi[li]+1,i,con(a[i]));
qx[++lx]=i; qi[++li]=i;
add(1,1,i,I);
for(auto j:q[i]) ans[j.id]=que(1,j.l,i)%mod;
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
T4 桥梁
先考虑暴力做法，暴力修改后遍历所有边，找出 满足条件的边，并查集维护连通性，然后查询。
考虑操作分块（怎么想到的？）。
设定块长为 \(S\)，那么我们将每 \(S\) 次操作划分为一块，这样块内的查询和修改操作都是小于等于 \(S\) 的，由此对于块内我们可以考虑一些暴力的操作。
仅看一个块内，我们把所有边按从大到小排序，查询也按从大到小排序，这样对于没被修改的边，加入的时候按查询的顺序加就好了，类似单调性？先加的边一定能满足后面的查询。
考虑会被修改的边，因为一个块内最多有 \(S\) 次修改操作，所以暴力将时间小于询问并且乘重大于询问加入连通块，用可撤销并查集维护，每次暴力修改 。
块长 \(\sqrt{n}\) 时复杂度 \(O(n\sqrt{n}\log(n))\)。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5,S = 1024;
int n,m,qq;
struct E {int u,v,w,id;} e[N];
struct Q {int id,bc,t;};
inline bool cmpe(E &x,E &y) {return x.w>y.w;}
inline bool cmpq(Q &x,Q &y) {return x.bc>y.bc;}
vector<Q> q,f;
int ys[N],vs[N],top,fa[N],sz[N],st[N],ans[N];
inline int find(int x) {return x==fa[x]?x:find(fa[x]);}
inline void merge(int u,int v)
{
u=find(u); v=find(v);
if(u==v) return;
if(sz[u]<sz[v]) swap(u,v);
st[++top]=v;
sz[u]+=sz[v],fa[v]=u;
}
inline void back(int lst)
{
while(top>lst)
{
int v=st[top--];
sz[fa[v]]-=sz[v];
fa[v]=v;
}
}
void work()
{
sort(e+1,e+1+m,cmpe);
sort(q.begin(),q.end(),cmpq);
for(int i=1;i<=m;i++) ys[e[i].id]=i;
vector<Q> tmp;
for(Q i:f) vs[i.id]=-1,tmp.push_back({i.id,e[ys[i.id]].w,0});
for(Q i:f) tmp.push_back(i);
for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
top=0;
for(int i=0,t=1;i<q.size();i++)
{
while(t<=m&&e[t].w>=q[i].bc)
{
if(!vs[e[t].id]) merge(e[t].u,e[t].v);
t++;
}
int lst=top;
for(Q x:tmp)
if(x.t<=q[i].t) vs[x.id]=x.bc;
for(Q x:f)
if(vs[x.id]>=q[i].bc) merge(e[ys[x.id]].u,e[ys[x.id]].v);
ans[q[i].t]=sz[find(q[i].id)];
back(lst);
}
for(Q i:f) e[ys[i.id]].w=i.bc,vs[i.id]=0;
f.clear(); q.clear();
}
int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z; scanf("%d%d%d",&x,&y,&z);
e[i]={x,y,z,i};
}
scanf("%d",&qq);
for(int i=1;i<=qq;i++)
{
int c,x,y; scanf("%d%d%d",&c,&x,&y);
c==1?f.push_back(Q{x,y,i}):q.push_back(Q{x,y,i});
if(i%S==0) work();
}
if(qq%S) work();
for(int i=1;i<=qq;i++) if(ans[i]) printf("%d\n",ans[i]);
return 0;
}