2024 1 月杂题
前言
shin nyan kwai le!
唉，SCOI2024。
CF896E Welcome home, Chtholly
这个信息看起来没有什么数据结构能维护，考虑暴力修改可不可行。
考虑值域是 $[1,V]$，那么分情况讨论：
- 若 $2x<V$，那么把 $[1,x]$ 加到 $(x,V]$ 上，再做一个全局减，值域减小。
- 若 $2x\ge V$，那么把 $(x,V]$ 加到 $[1,x]$ 上，值域减小。
容易发现每次修改值域都会减小，势能分析复杂度是值域大小的。
那么考虑分块，散块暴力维护，考虑中间整块用什么数据结构刻画。
容易发现可以 dsu，对每个连通块记一个颜色，再对每个颜色存对应连通块即可。
复杂度 $O((n+m+V)\sqrt{n}\cdot\alpha(n))$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,T=400,inf=0x3f3f3f3f;
int n,m,a[N],ans[N],vis[N];
int fa[N],sz[N],co[N],mp[N];
int L[N],R[N],blg[N];
struct query{
int pos,op,l,r,x;
bool operator <(const query &p)const{return pos<p.pos;}
};
vector<query> add[N],del[N];
set<query> ss;
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
void Merge(int u,int v){
int fu=getfa(u),fv=getfa(v);
if(fu==fv) return;
sz[fv]+=sz[fu];
fa[fu]=fv;
}
void init(int L,int R,int &mx,int &tag){
mx=tag=0;
forup(j,L,R){
mx=max(mx,a[j]);
fa[j]=j,sz[j]=1,mp[a[j]]=0,co[j]=a[j];
}
forup(j,L,R){
if(mp[a[j]]){
Merge(j,mp[a[j]]);
}else{
mp[a[j]]=j;
}
}
}
signed main(){
n=read();m=read();
forup(i,1,n){
a[i]=read();
}
int tt=n/T;
forup(i,1,tt){
L[i]=R[i-1]+1;R[i]=i*T;
forup(j,L[i],R[i]){
blg[j]=i;
}
}
if(R[tt]!=n){
++tt;
L[tt]=R[tt-1]+1;R[tt]=n;
forup(j,L[tt],R[tt]){
blg[j]=tt;
}
}
forup(i,1,m){
int op=read(),l=read(),r=read(),x=read();
if(op==2) vis[i]=1;
query nw=query{i,op,l,r,x};
add[blg[l]].push_back(nw);
del[blg[r]+1].push_back(nw);
}
forup(i,1,tt){
int mx=0,tag=0;
for(auto j:add[i]) ss.insert(j);
for(auto j:del[i]) ss.erase(j);
init(L[i],R[i],mx,tag);
for(auto j:ss){
int pos=j.pos,op=j.op,l=j.l,r=j.r,x=j.x;
if(l<=L[i]&&R[i]<=r){
if(op==1){
if(mx<=x) continue;
if(x*2>=mx){
forup(i,tag+x+1,tag+mx){
if(!mp[i]) continue;
if(mp[i-x]){
Merge(mp[i],mp[i-x]);
}else{
mp[i-x]=mp[i];
co[getfa(mp[i-x])]=i-x;
}
mp[i]=0;
}
mx=x;
}else{
forup(i,tag+1,tag+x){
if(!mp[i]) continue;
if(mp[i+x]){
Merge(mp[i],mp[i+x]);
}else{
mp[i+x]=mp[i];
co[getfa(mp[i+x])]=i+x;
}
mp[i]=0;
}
tag+=x;
mx-=x;
}
}else{
if(x<=mx&&mp[tag+x]){
ans[pos]+=sz[getfa(mp[tag+x])];
}
}
}else{
forup(k,L[i],R[i]) a[k]=co[getfa(k)]-tag;
forup(k,L[i],R[i]) co[k]=mp[a[k]+tag]=0;
l=max(l,L[i]);r=min(r,R[i]);
if(op==1){
forup(k,l,r){
if(a[k]>x) a[k]-=x;
}
}else{
forup(k,l,r){
if(a[k]==x) ++ans[pos];
}
}
init(L[i],R[i],mx,tag);
}
}
forup(k,L[i],R[i]) a[k]=co[getfa(k)]-tag;
forup(k,L[i],R[i]) co[k]=mp[a[k]+tag]=0;
}
forup(i,1,m){
if(vis[i]){
printf("%d\n",ans[i]);
}
}
}
P5501 [LnOI2019] 来者不拒，去者不追
一眼莫队。
具体来说，把贡献改为 $\sum_{x\in[l,r]}\left(a_x+a_x\times \sum_{y\in[l,r]}[y<x]\right)$，然后 $a_x$ 就是区间和，后面那个东西可以莫队维护。具体就是对于每个数维护区间内严格小于它的数的个数和严格大于它的数的总和。
莫队二次离线 $+$ 值域分块可以压到 $O(n\sqrt{V}+n\sqrt{n}+m\sqrt{n})$，注意值域分块要 $O(\sqrt{V})$ 修改 $O(1)$ 查询。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=5e5+5,T=500;
i64 L[N],R[N],blg[N],MX,pres[N];
i64 n,m,a[N],tt;
i64 ans[N];
struct query{
i64 l,r,pos;
};
namespace block{
const int SN=380,N=1e5;
i64 sob[SN],ss[N],sob2[SN],ss2[N];
int L[SN],R[SN],blg[N];
void init(){
tt=MX/T;
forup(i,1,tt){
L[i]=R[i-1]+1;R[i]=i*T;
forup(j,L[i],R[i]){
blg[j]=i;
}
}
if(R[tt]!=MX){
++tt;
L[tt]=R[tt-1]+1;R[tt]=MX;
forup(j,L[tt],R[tt]){
blg[j]=tt;
}
}
}
void upd(i64 x,i64 k){
forup(i,blg[x]+1,tt) sob[i]+=k;
forup(i,x+1,R[blg[x]]) ss[i]+=k;
}
void upd2(i64 x,i64 k){
fordown(i,blg[x]-1,1) sob2[i]+=k;
fordown(i,x-1,L[blg[x]]) ss2[i]+=k;
}
i64 sum(i64 x){
return sob[blg[x]]+ss[x];
}
i64 sum2(i64 x){
return sob2[blg[x]]+ss2[x];
}
}
namespace sub2{
vector<query> qp[N],qs[N],q[N];
i64 pre[N],suf[N];
void solve(){
block::init();
forup(i,1,n){
block::upd(a[i],1);block::upd2(a[i],a[i]);
pre[i+1]=pre[i]+block::sum(a[i+1])*a[i+1]+block::sum2(a[i+1]);
for(auto j:qp[i]){
i64 f=-1,pos=j.pos,l=j.l,r=j.r;
if(pos<0){f=-f;pos=-pos;}
forup(k,l,r) ans[pos]+=(block::sum(a[k])*a[k]+block::sum2(a[k]))*f;
}
}
mem(block::sob,0);mem(block::ss,0);mem(block::sob2,0);mem(block::ss2,0);
fordown(i,n,1){
block::upd(a[i],1);block::upd2(a[i],a[i]);
suf[i-1]=suf[i]+block::sum(a[i-1])*a[i-1]+block::sum2(a[i-1]);
for(auto j:qs[i]){
i64 f=-1,pos=j.pos,l=j.l,r=j.r;
if(pos<0){f=-f;pos=-pos;}
forup(k,l,r) ans[pos]+=(block::sum(a[k])*a[k]+block::sum2(a[k]))*f;
}
}
forup(i,1,m){
for(auto j:q[i]){
i64 f=1,pos=j.pos,l=j.l,r=j.r;
if(pos<0){
f=-f;pos=-pos;
}
if(pos==1){
ans[i]+=(pre[r]-pre[l-1])*f;
}else{
ans[i]+=(suf[l]-suf[r+1])*f;
}
}
}
}
}
namespace sub1{
query q[N];
void solve(){
tt=n/T;
forup(i,1,tt){
L[i]=R[i-1]+1;R[i]=i*T;
forup(j,L[i],R[i]){
blg[j]=i;
}
}
if(R[tt]!=MX){
++tt;
L[tt]=R[tt-1]+1;R[tt]=MX;
forup(j,L[tt],R[tt]){
blg[j]=tt;
}
}
stable_sort(q+1,q+m+1,[&](query a,query b){
if(blg[a.l]==blg[b.l]){
if(blg[a.l]&1){
return a.r<b.r;
}else{
return a.r>b.r;
}
}else{
return blg[a.l]<blg[b.l];
}
});
i64 L=1,R=0;
forup(i,1,m){
if(R<q[i].r){
sub2::qp[L-1].push_back(query{R+1,q[i].r,q[i].pos});
sub2::q[q[i].pos].push_back(query{R+1,q[i].r,1});
R=q[i].r;
}
if(L>q[i].l){
sub2::qs[R+1].push_back(query{q[i].l,L-1,q[i].pos});
sub2::q[q[i].pos].push_back(query{q[i].l,L-1,2});
L=q[i].l;
}
if(R>q[i].r){
sub2::qp[L-1].push_back(query{q[i].r+1,R,-q[i].pos});
sub2::q[q[i].pos].push_back(query{q[i].r+1,R,-1});
R=q[i].r;
}
if(L<q[i].l){
sub2::qs[R+1].push_back(query{L,q[i].l-1,-q[i].pos});
sub2::q[q[i].pos].push_back(query{L,q[i].l-1,-2});
L=q[i].l;
}
}
}
}
signed main(){
n=read();m=read();
forup(i,1,n){
a[i]=read();
pres[i]=pres[i-1]+a[i];
MX=max(MX,a[i]);
}
forup(i,1,m){
sub1::q[i].l=read();sub1::q[i].r=read();sub1::q[i].pos=i;
}
sub1::solve();
sub2::solve();
forup(i,1,m) ans[sub1::q[i].pos]+=ans[sub1::q[i-1].pos];
forup(i,1,m) ans[sub1::q[i].pos]+=pres[sub1::q[i].r]-pres[sub1::q[i].l-1];
forup(i,1,m) printf("%lld\n",ans[i]);
}
CF1648D Serious Business
妙题。
考虑最后肯定会从第二层的某个可操作区间向下走一步到第三层，那么考虑从哪个地方进入这个区间。
容易发现进入有两种，一种是从左侧进入，另一种是从上方，第一层下来。
那么设 $dp_{i}$ 表示进入（可能存在的）某个包含 $a_{2,i}$ 的区间前（或者说不得不对这个区间进行操作前），能得到的最大贡献，即到达 $a_{1,i}$ 和 $a_{2,i-1}$ 两点的最大贡献其中的较大值。
首先到达 $a_{1,i}$ 的路线只有一种，故 $dp_i$ 初始等于 $a_1$ 的前缀和。
然后考虑第二种。在不得不对某个区间操作时，上一步的位置必定是另一个区间的右端点，故可以枚举“上一步”所对应的区间。具体来说，对于一个区间 $(l,r,x)$，有转移 $dp_{r+1}\gets s_r-x+\max_{i=l}^r\begin{Bmatrix}dp_i-s_i-1\end{Bmatrix}$，其中 $s$ 是 $a_2$ 的前缀和。这一个按 $r$ 从小到大转移即可。
现在考虑从前文的“最后一个区间”具体哪个位置进入第三行。即对于每个 $i$，求出：
$$\max_{k}^{l_k\le i\le r_k}\begin{Bmatrix}(dp_i+t_n-s_{i-1})+\max_{j=i}^{r_k}\begin{Bmatrix}s_i-t_{i-1}-x_k\end{Bmatrix}\end{Bmatrix}$$
其中 $k$ 是枚举一个包含 $i$ 的区间，$t$ 是 $a_3$ 的前缀和。这里跳步了，但我觉得这个式子很好理解。
那么这个可以线段树维护，具体来说，每遇到一个 $l$ 就用 $x$ 更新 $[l,r]$，然后查询 $[i,n]$。
复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=5e5+5,M=1<<19,inf=1e18;
i64 n,m,a[N][3],dp[N];
struct range{
i64 l,r,x;
};
vector<range> rg[N],rgl[N];
struct zkw{
i64 mx[M<<1];
void Build(){
forup(i,1,M+n) mx[i]=-inf;
}
void Update(i64 P,i64 X){
for(i64 i=P+M;i;i>>=1) mx[i]=max(mx[i],X);
}
i64 Query(i64 l,i64 r){
i64 res=-inf;
for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
if(!(l&1)) res=max(res,mx[l^1]);
if( r&1 ) res=max(res,mx[r^1]);
}
return res;
}
}mt;
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
i64 queryval[N<<2],querymax[N<<2],mark[N<<2];
void PushUp(i64 id){
querymax[id]=max(querymax[id<<1],querymax[id<<1|1]);
}
void PushDown(i64 id){
querymax[id<<1]=max(querymax[id<<1],queryval[id<<1]+mark[id]);
querymax[id<<1|1]=max(querymax[id<<1|1],queryval[id<<1|1]+mark[id]);
mark[id<<1]=max(mark[id<<1],mark[id]);
mark[id<<1|1]=max(mark[id<<1|1],mark[id]);
mark[id]=-inf;
}
void Build(i64 l=1,i64 r=n,i64 id=1){
mark[id]=-inf;
if(l==r){
queryval[id]=a[l][1]-a[l-1][2];
querymax[id]=-inf;
return;
}
Build(lson);Build(rson);
PushUp(id);
queryval[id]=max(queryval[id<<1],queryval[id<<1|1]);
}
void Update(i64 L,i64 R,i64 X,i64 l=1,i64 r=n,i64 id=1){
if(L<=l&&r<=R){
querymax[id]=max(querymax[id],queryval[id]+X);
mark[id]=max(mark[id],X);
return;
}
if(mark[id]!=-inf) PushDown(id);
if(L<=mid) Update(L,R,X,lson);
if(mid< R) Update(L,R,X,rson);
PushUp(id);
}
i64 Query(i64 L,i64 R,i64 l=1,i64 r=n,i64 id=1){
if(L<=l&&r<=R){
return querymax[id];
}
if(mark[id]!=-inf) PushDown(id);
i64 res=-inf;
if(L<=mid) res=max(res,Query(L,R,lson));
if(mid< R) res=max(res,Query(L,R,rson));
return res;
}
}t1;
signed main(){
n=read();m=read();
forup(i,0,2){
forup(j,1,n){
a[j][i]=read();
}
}
forup(i,1,n){
forup(j,0,2){
a[i][j]+=a[i-1][j];
}
dp[i]=a[i][0];
}
forup(i,1,m){
i64 l=read(),r=read(),x=read();
rg[r].push_back(range{l,r,x});
rgl[l].push_back(range{l,r,x});
}
mt.Build();
forup(i,1,n){
mt.Update(i,dp[i]-a[i-1][1]);
for(auto j:rg[i]){
dp[i+1]=max(dp[i+1],a[i][1]-j.x+mt.Query(j.l,j.r));
}
}
t1.Build();
i64 ans=-inf;
forup(i,1,n){
for(auto j:rgl[i]){
t1.Update(j.l,j.r,-j.x);
}
ans=max(ans,dp[i]+a[n][2]-a[i-1][1]+t1.Query(i,n));
}
printf("%lld\n",ans);
}
P5610 [Ynoi2013] 大学
做法不难，但是要卡常。
考虑一个数的因数个数上界大约是 $\sqrt[3]{n}$，那么把每个数在所有因数的位置存一下空间就是 $n\sqrt[3]{V}$ 的。那么就可以存下来然后暴力修改。由于每个数质因数最多不超过 $\log V$ 个，所以最多被除 $\log V$ 次，势能分析删除次数是 $O(n\log V)$ 的。然后每次可以 $O(\log n)$ 二分找到对应区间内第一个 $x$ 倍数的位置，然后每次暴力修改，复杂度是对的。
那么现在只有删除无法处理，除去在序列上删数复杂度是 $O(m\log n+n\log V)$ 的。删数乍一看可以平衡树，但这是 ynoi，过不了。
可以用动态数组 $+$ 并查集，每个并查集就是连续的被删的区间，这部分复杂度是 $O(n\alpha(n)d(n))$。
然后 vector 据说过不了。考虑开内存池/链式前向星。
《稍微卡一卡》就能过了。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(register int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
typedef long long i64;
char *p1,*p2,buf[1<<21];
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline i64 read(){
i64 x=0;char c=gc;
while(c<'0'||c>'9')c=gc;
while('0'<=c&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x;
}
#undef gc
const int N=1e5+5,M=5e5+5;
int n,m,a[N],mx;
struct edge{
int v,nxt;
edge(int _v=0,int _nxt=0):v(_v),nxt(_nxt){};
}e[M*18];
int head[M],cnte;
int sz[M],pool[M*85],*nowpo=pool;
int *fa[M],*pos[M];
inline int *New(int sz){
nowpo+=sz;
return nowpo-sz;
}
inline int getfa(int p,int x){return x==fa[p][x]?x:fa[p][x]=getfa(p,fa[p][x]);}
i64 c[N];
inline void upd(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
inline i64 sum(int x){i64 res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
int stk[N],top;
signed main(){
n=read();m=read();
forup(i,1,n){
a[i]=read();
if(a[i]>mx) mx=a[i];
c[i]+=a[i];
if(i+(i&-i)<=n) c[i+(i&-i)]+=c[i];
}
forup(i,2,mx){
for(register int j=i;j<=mx;j+=i){
e[++cnte]=edge(i,head[j]);head[j]=cnte;
}
}
forup(i,1,n){
for(register int j=head[a[i]];j;j=e[j].nxt){
++sz[e[j].v];
}
}
forup(i,2,mx) fa[i]=New(sz[i]+1);
forup(i,2,mx){
forup(j,0,sz[i]){
fa[i][j]=j;
}
}
forup(i,2,mx){
pos[i]=New(sz[i]+1);
pos[i][sz[i]]=n+1;
}
mem(sz,0);
forup(i,1,n){
for(register int j=head[a[i]];j;j=e[j].nxt){
pos[e[j].v][sz[e[j].v]++]=i;
}
}
i64 lans=0;
while(m--){
int op=read();
if(op==1){
i64 l=read(),r=read(),x=read();
l^=lans;r^=lans;x^=lans;
if(!sz[x]) continue;
int st=std::lower_bound(pos[x],pos[x]+sz[x],l)-pos[x];
st=getfa(x,st);
int i;
for(i=st;pos[x][i]<=r;i=getfa(x,i+1)){
int &v=a[pos[x][i]];
if(v%x==0){
upd(pos[x][i],v/x-v);
v/=x;
}
if(v%x!=0){
stk[top++]=i;
}else{
while(top){
fa[x][getfa(x,stk[top-1])]=getfa(x,i);
top--;
}
}
}
while(top){
fa[x][getfa(x,stk[top-1])]=getfa(x,i);
top--;
}
}else{
i64 l=read(),r=read();
l^=lans;r^=lans;
lans=sum(r)-sum(l-1);
printf("%lld\n",lans);
}
}
}
P5609 [Ynoi2013] 对数据结构的爱/CF1172F Nauuo and Bug
个更新 $c_{u,x+y}$。
那么稍微推一推式子，可以得到若 $c_{ls,x+1}-1+sum_{ls 传送门 传送门2
这玩意看起来不好刻画。这种可以考虑用线段树维护一个函数，表示“从该区间左侧读入一个值一直操作到该区间右侧”得到的贡献。然后查询就是把对应区间取出来顺次跑一遍。设线段树结点 $i$ 的函数为 $f(i,x)$
容易发现，假如求出了区间 $i$ 减 $k$ 次 $p$ 所需要读入的最小值 $c_{i,k}$，那么每次遇到一个 $x$，可以在 $c_i$ 上二分求出需要减多少次，然后就能求 $f(i,x)$ 了。求单个 $f$ 复杂度是 $O(\log V)$，合起来就是 $O(\log n\log V)$。并且由于结点内 $c_{i,k}$ 的第二维 $k$ 显然不超过区间长度（呃其实是区间长度 $+1$，因为还有个 $0$），所以空间复杂度也是对的。
为方便叙述，假设现在把 $ls,rs$ 两结点合并到 $u$ 上。
叶子结点的 $c$ 很显然，考虑怎么合并。一个简单的想法是若 $c_{ls,x+1}-1$（即能在左边减 $x$ 次的最大值）经过左儿子后得到的数大于等于 $c_{rs,y}$，那么就有可能用这两}-xp\ge c_{rs,y}$，则 $c_{u,x+y}\gets \max(c_{ls,x},c_{rs,y}-sum_{ls}+xp)$（这里的 $\gets$ 指与原有值取 $\min$）。
那么直接做就是 $O(n^2)$ 的，但是这个又不是很好刻画。这种和两边下标都强相关的可以考虑寻找单调性。
令 $g(x,y)=\max(c_{ls,x},c_{rs,y}-sum_{ls}+xp)$（若不合法则为空），猜测 $g(x,y)\le g(x+1,y-1)$。
首先，对任意 $u,x$ 对，有 $c_{u,x+1}>c_{u,x}$，或者更准确地，有 $c_{u,x+1}\ge c_{u,x}+p$。因为当读入值取到 $c_{u,x}$，那么在区间上从左到右暴力计算的时候，图像大致是一堆从 $0$ 到 $p$ 的分段曲线。那么必然有一个地方能恰好取到 $0$，并且后面都非正。而为了让这个地方超过 $p$ 显然初值要至少增加 $p$（考虑它前面的向上平移不会使 $-p$ 次数增加，后面的会比它晚增加）。
考虑证明 $c_{rs,y}-sum_{ls}+xp\le c_{ls,x+1}$，这样就能推出 $g(x,y)\le c_{ls,x+1}\le g(x+1,y-1)$ 了。
由于 $g(x,y)$ 在合法时才存在，故 $c_{ls,x+1}-1+sum_{ls}-xp\ge c_{rs,y}$，则直接有 $c_{rs,y}-sum_{ls}+(x+1)p\le c_{ls,x+1}$。
那么具体实现时，用一个指针维护 $y$，注意每次 $x$ 增加时需要 $-1$。
预处理复杂度 $O(n\log n)$，查询复杂度 $O(m\log n\log V)$。
代码最小清新的一集。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=1e6+5,inf=1e18;
i64 n,m,p,a[N];
struct SegTree{
#define mid ((l+r)>>1)
#define ls id<<1
#define rs id<<1|1
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
vector<i64> c[N<<2];
vector<int> vec;
i64 sum[N<<2];
void Build(i64 l=1,i64 r=n,i64 id=1){
c[id].resize(r-l+2,inf);
if(l==r){
sum[id]=a[l];
c[id][0]=-inf;
c[id][1]=p-a[l];
return;
}
Build(lson);Build(rson);
sum[id]=sum[ls]+sum[rs];
int y=0;
forup(x,0,(mid-l)){
while(y<=(r-mid)&&c[rs][y]<=c[ls][x+1]-1+sum[ls]-x*p){
c[id][x+y]=min(c[id][x+y],max(c[ls][x],c[rs][y]-sum[ls]+x*p));
++y;
}
if(y) --y;
}
int x=mid-l+1;
while(y<=r-mid){
c[id][x+y]=min(c[id][x+y],max(c[ls][x],c[rs][y]-sum[ls]+x*p));
++y;
}
}
void Query(int L,int R,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
vec.push_back(id);
return;
}
if(L<=mid) Query(L,R,lson);
if(mid< R) Query(L,R,rson);
}
i64 Ask(int L,int R){
vec.clear();
Query(L,R);
i64 res=0;
for(auto i:vec){
int ll=0,rr=c[i].size()-1,mm;
while(ll<rr){
mm=(ll+rr+1)>>1;
if(c[i][mm]<=res) ll=mm;
else rr=mm-1;
}
res=res+sum[i]-ll*p;
}
return res;
}
}mt;
signed main(){
n=read();m=read();p=read();
forup(i,1,n){
a[i]=read();
}
mt.Build();
forup(i,1,m){
int l=read(),r=read();
printf("%lld\n",mt.Ask(l,r));
}
}
P5280 [ZJOI2019] 线段树
核心思路是在一棵线段树上维护所有线段树的答案。
考虑设 $f_u$ 表示现在有多少棵线段树在结点 $u$ 处有 tag。
那么把一棵线段树上的结点分成五类：
假设要修改红色区间内。
首先是修改路径上经过的结点（就是上图中橙色点），这一部分会把原有的 tag 清空。然后是区间对应的最下面的结点，就是蓝色部分，这一部分会产生新的 tag。接下来是修改路径上的“另一个儿子”（黄色部分），但这一步的贡献和上面原本有没有 tag 有关，怎么办呢？考虑再记一个 $g_u$ 表示从 $u$ 到根的路径上有多少棵树上没有 tag（为了方便转移记没有的个数）。那么转移就很简单了：
为方便叙述，$f,g$ 为原有状态，$f',g'$ 为转移后的状态，$w$ 为这一次操作之前的线段树数量。
对于橙色点：
$$ \begin{cases} f_u'=f_u+0\\ g_u'=g_u+w \end{cases} $$
对于蓝色点：
$$ \begin{cases} f_u'=f_u+w\\ g_u'=g_u+0 \end{cases} $$
对于黄色点：
$$ \begin{cases} f_u'=f_u+(w-g_u)\\ g_u'=g_u+0 \end{cases} $$
对于白色点：
$$ \begin{cases} f_u'=f_u+f_u\\ g_u'=g_u+0 \end{cases} $$
对于灰色点：
$$ \begin{cases} f_u'=f_u+f_u\\ g_u'=g_u+g_u \end{cases} $$
然后就可以直接维护了，复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,mod=998244353;
int n,m,w=1;
struct SegTree{
#define mid ((l+r)>>1)
#define ls id<<1
#define rs id<<1|1
#define lson l,mid,ls
#define rson mid+1,r,rs
int sum[N<<2],f[N<<2],g[N<<2],markf[N<<2],markg[N<<2];
void PushUp(int id){
sum[id]=((sum[ls]+sum[rs])%mod+f[id])%mod;
}
void modi(int id,int mf,int mg){
sum[id]=1ll*sum[id]*mf%mod;
f[id]=1ll*f[id]*mf%mod;
g[id]=1ll*g[id]*mg%mod;
markf[id]=1ll*markf[id]*mf%mod;
markg[id]=1ll*markg[id]*mg%mod;
}
void PushDown(int id){
modi(ls,markf[id],markg[id]);
modi(rs,markf[id],markg[id]);
markf[id]=markg[id]=1;
}
void Build(int l=1,int r=n,int id=1){
markg[id]=markf[id]=1;
g[id]=1;
if(l==r) return;
Build(lson);Build(rson);
}
void MO4(int l,int r,int id){
(f[id]+=w)%=mod;
if(l!=r){
PushDown(id);
modi(ls,2,1);
modi(rs,2,1);
PushUp(id);
}else{
sum[id]=f[id];
}
}
void MO5(int l,int r,int id){
(f[id]+=(w+mod-g[id])%mod)%=mod;
(g[id]*=2)%=mod;
if(l!=r){
PushDown(id);
modi(ls,2,2);
modi(rs,2,2);
PushUp(id);
}else{
sum[id]=f[id];
}
}
void Modify(int L,int R,int l=1,int r=n,int id=1){
if(l^r) PushDown(id);
if(L<=l&&r<=R){
MO4(l,r,id);
return;
}
(g[id]+=w)%=mod;
if(R<=mid){
Modify(L,R,lson);
MO5(rson);
}else if(L>mid){
Modify(L,R,rson);
MO5(lson);
}else{
Modify(L,R,lson);
Modify(L,R,rson);
}
PushUp(id);
}
int Query(){
return sum[1];
}
}mt;
signed main(){
n=read();m=read();
mt.Build();
forup(i,1,m){
int op=read();
if(op==1){
int l=read(),r=read();
mt.Modify(l,r);
(w<<=1)%=mod;
}else{
printf("%d\n",mt.Query());
}
}
}
P6773 [NOI2020] 命运
考虑树形 DP。
容易想到若两条路径为 $(u_1,v)$ 和 $(u_2,v)$，其中 $u_1$ 是 $u_2$ 的祖先（等价于 $u_2$ 的深度大于等于 $u_1$）。那么满足了 $u_2$ 就必定满足 $u_1$。
考虑一个更强的性质，假如对于点 $x$ ，有许多路径 $(u,v)$ 满足 $u$ 是 $x$ 的祖先，$v$ 在 $x$ 的子树内。那么如果只考虑在 $x$ 到根的路径上涂色的话，只要其中最深的 $u$ 满足了其余必定都满足了。
容易想到设 $dp_{u,i}$ 表示只考虑下端点在 $u$ 子树内的路径，最深的没被满足的上端点是多少。特别的，令 $dp_{u,0}$ 表示下端点在 $u$ 子树内的所有路径全满足的情况。
那么转移就枚举 $u$ 的儿子 $v$，然后考虑边 $(u,v)$ 要不要涂黑。分涂黑和不涂黑两种：
涂黑：
$$dp_{u,i}\gets \sum_{j=0}^{depth_u}dp_{u,i}\cdot dp_{v,j}$$
因为此时不满足的路径必定从 $u$ 中贡献，$v$ 中所有小于等于 $depth_u$ 的 $i$ 都能被满足。
不涂黑：
$$dp_{u,i}\gets \sum_{j=0}^idp_{u,i}\cdot dp_{v,j}+\sum_{j=0}^{i-1}dp_{u,j}\cdot dp_{v,i}$$
因为最深的可能从 $u$ 中产生，也可能从 $v$ 中产生。后一个 $j$ 只枚举到 $i-1$ 是为了防止算重。
容易发现有很多前缀和，设 $g_{u,i}=\sum_{j=0}^idp_{u,j}$，则有：
$$dp_{u,i}\gets dp_{u,i}(g_{v,depth_u}+g_{v,i})+g_{u,i-1}\cdot dp_{v,i}$$
然后就能 $O(n^2)$ 做了。
考虑优化，容易发现这个可以线段树合并，其中 $g_{v,depth_u}$ 是常数，而 $g_{v,i}$ 和 $g_{u,i-1}$ 可以利用线段树中序遍历的性质维护。
复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5e5+5,mod=998244353;
int n,m;
vector<int> e[N];
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,ls[id]
#define rson mid+1,r,rs[id]
int ls[N*20],rs[N*20],sum[N*20],mark[N*20],root[N],cntn;
int New(){
int nw=++cntn;
ls[nw]=rs[nw]=sum[nw]=0;
mark[nw]=1;
return nw;
}
void PushUp(int id){
sum[id]=(sum[ls[id]]+sum[rs[id]])%mod;
}
void PushDown(int id){
if(mark[id]==1) return;
if(ls[id]){
sum[ls[id]]=1ll*sum[ls[id]]*mark[id]%mod;
mark[ls[id]]=1ll*mark[ls[id]]*mark[id]%mod;
}
if(rs[id]){
sum[rs[id]]=1ll*sum[rs[id]]*mark[id]%mod;
mark[rs[id]]=1ll*mark[rs[id]]*mark[id]%mod;
}
mark[id]=1;
}
void Update(int P,int l,int r,int &id){
if(!id) id=New();
if(l==r){
sum[id]=1;
return;
}
if(P<=mid) Update(P,lson);
else Update(P,rson);
PushUp(id);
}
int Merge(int l,int r,int &su,int &sv,int u,int v){
if(!u&&!v) return 0;
if(!u||!v){
if(!u){
(sv+=sum[v])%=mod;
sum[v]=1ll*sum[v]*su%mod;
mark[v]=1ll*mark[v]*su%mod;
return v;
}else{
(su+=sum[u])%=mod;
sum[u]=1ll*sum[u]*sv%mod;
mark[u]=1ll*mark[u]*sv%mod;
return u;
}
}else if(l==r){
int cu=sum[u];
(sv+=sum[v])%=mod;
sum[u]=(1ll*sum[u]*sv%mod+1ll*su*sum[v]%mod)%mod;
(su+=cu)%=mod;
return u;
}
PushDown(u);PushDown(v);
ls[u]=Merge(l,mid,su,sv,ls[u],ls[v]);
rs[u]=Merge(mid+1,r,su,sv,rs[u],rs[v]);
PushUp(u);
return u;
}
int Query(int L,int R,int l,int r,int id){
if(!id) return 0;
if(L<=l&&r<=R){
return sum[id];
}
PushDown(id);
int res=0;
if(L<=mid) (res+=Query(L,R,lson))%=mod;
if(mid< R) (res+=Query(L,R,rson))%=mod;
return res;
}
}mt;
vector<int> vec[N];
int dpt[N];
void dfs(int x,int fa){
dpt[x]=dpt[fa]+1;
int hst=0;
for(auto i:vec[x]){
if(dpt[i]>hst){
hst=dpt[i];
}
}
mt.Update(hst,0,n,mt.root[x]);
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
int su=0,sv=mt.Query(0,dpt[x],0,n,mt.root[i]);
mt.root[x]=mt.Merge(0,n,su,sv,mt.root[x],mt.root[i]);
}
}
signed main(){
n=read();
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
m=read();
forup(i,1,m){
int u=read(),v=read();
vec[v].push_back(u);
}
dfs(1,0);
printf("%d\n",mt.Query(0,0,0,n,mt.root[1]));
}
P7219 [JOISC2020] 星座 3
首先，最小化删掉的权值和等价于最大化剩下的权值和。故考虑留下尽可能多的星星，这道题应该怎么做。
根据题意，两颗星星不能同时存在，当且仅当包含它们的最小矩形中没有任何白色部分。也就是说，考虑最高的白色部分，它的上方只能有一颗星星。而从它分开的两个区间，容易发现是类似的子问题。
容易发现这是一个笛卡尔树的形式。那么就把“合法”转化成了对于任意一棵笛卡尔树的子树，保留至多一颗高于根节点的星星。
容易想到 DP。设 $dp_{u,i}$ 表示考虑 $u$ 的子树，保留的星星最高为 $i$ 的最大贡献和。
转移大概是一个前缀最大值。然后就能用和上一道题类似的方法维护了，此处略过。
复杂度 $O(n\log n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5;
const i64 inf=1e18;
int n,m,h[N];
int ST[19][N];
void initst(){
forup(i,1,n){
ST[0][i]=i;
}
forup(i,0,17){
forup(j,1,n-(1<<(i+1))+1){
ST[i+1][j]=h[ST[i][j]]>h[ST[i][j+(1<<i)]]?ST[i][j]:ST[i][j+(1<<i)];
}
}
}
int Query(int l,int r){
int len=31^__builtin_clz(r-l+1);
return h[ST[len][l]]>h[ST[len][r-(1<<len)+1]]?ST[len][l]:ST[len][r-(1<<len)+1];
}
vector<int> e[N];
int rt;
void Build(int l,int r,int rt){
if(l>r) return;
int x=Query(l,r);
e[rt].push_back(x);
Build(l,x-1,x);Build(x+1,r,x);
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,ls[id]
#define rson mid+1,r,rs[id]
int ls[N*18],rs[N*18],root[N],cntn;
i64 querymax[N*18],mark[N*18];
void PushUp(int id){
querymax[id]=max(querymax[ls[id]],querymax[rs[id]]);
}
void PushDown(int id){
if(mark[id]){
if(ls[id]){
querymax[ls[id]]+=mark[id];
mark[ls[id]]+=mark[id];
}
if(rs[id]){
querymax[rs[id]]+=mark[id];
mark[rs[id]]+=mark[id];
}
mark[id]=0;
}
}
void Update(int P,i64 X,int l,int r,int &id){
if(!id) id=++cntn;
if(l==r){
querymax[id]=max(querymax[id],X);
return;
}
if(P<=mid) Update(P,X,lson);
else Update(P,X,rson);
PushUp(id);
}
i64 Query(int L,int R,int l,int r,int id){
if(!id) return 0;
if(L<=l&&r<=R){
return querymax[id];
}
PushDown(id);
i64 res=0;
if(L<=mid) res=max(res,Query(L,R,lson));
if(mid< R) res=max(res,Query(L,R,rson));
return res;
}
int Merge(int H,int l,int r,i64 &mu,i64 &mv,int u,int v){
if(!u&&!v) return 0;
if(!u||!v){
if(!u){
mv=max(mv,Query(1,H,l,r,v));
querymax[v]+=mu;
mark[v]+=mu;
return v;
}else{
mu=max(mu,Query(1,H,l,r,u));
querymax[u]+=mv;
mark[u]+=mv;
return u;
}
}else if(l==r){
if(l<=H){
mv=max(mv,querymax[v]);
mu=max(mu,querymax[u]);
}
querymax[u]=max(querymax[u]+mv,querymax[v]+mu);
return u;
}
PushDown(u);PushDown(v);
ls[u]=Merge(H,l,mid,mu,mv,ls[u],ls[v]);
rs[u]=Merge(H,mid+1,r,mu,mv,rs[u],rs[v]);
PushUp(u);
return u;
}
}mt;
void dfs(int x){
for(auto i:e[x]){
dfs(i);
i64 mu=0,mv=0;
mt.root[x]=mt.Merge(h[x],1,n,mu,mv,mt.root[x],mt.root[i]);
}
}
signed main(){
n=read();
forup(i,1,n){
h[i]=read();
}
initst();
rt=Query(1,n);
Build(1,rt-1,rt);Build(rt+1,n,rt);
m=read();
i64 sum=0;
forup(i,1,m){
int x=read(),y=read(),c=read();
sum+=c;
mt.Update(y,c,1,n,mt.root[x]);
}
dfs(rt);
printf("%lld\n",sum-mt.Query(1,n,1,n,mt.root[rt]));
}
CF1137F Matches Are Not a Child's Play
考虑一个很显然的结论：若钦定编号最大的点为根（这个点显然最后删掉），$u$ 在 $v$ 之前删掉当且仅当 $v$ 是 $u$ 的祖先或 $u$ 子树内编号最大值小于 $v$ 子树内编号最大值。
那么容易想到维护子树内编号最大值（为方便叙述，称这个值为“颜色”），那么一个点的排名就是颜色严格小于它的点数加上和它颜色相同的点中深度大于它的（其实就是和对应的这个“最大点”的距离）。因为要换根所以容易想到用 LCT 维护。然后再用 BIT 之类的东西维护颜色的前缀和就做完了。
复杂度 $O(n\log^2 n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,inf=0x3f3f3f3f;
int n,m,num[N];
vector<int> e[N];
struct BIT{
int c[N<<1];
void upd(int x,int k){for(;x<=n+m;x+=x&-x)c[x]+=k;}
int sum(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}t1;
struct LCT{
int ch[N][2],fa[N],revtag[N],coltag[N],co[N],sz[N];
#define get(x) (ch[fa[x]][1]==x)
#define isRoot(x) (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x)
void PushUp(int p){
sz[p]=sz[ch[p][0]]+1+sz[ch[p][1]];
}
void PushDown(int p){
if(revtag[p]){
auto work=[&](int x){
revtag[x]^=1;
swap(ch[x][0],ch[x][1]);
};
if(ch[p][0]) work(ch[p][0]);
if(ch[p][1]) work(ch[p][1]);
revtag[p]=0;
}
if(coltag[p]){
auto work=[&](int x,int c){
coltag[x]=c;
co[x]=c;
};
if(ch[p][0]) work(ch[p][0],coltag[p]);
if(ch[p][1]) work(ch[p][1],coltag[p]);
coltag[p]=0;
}
}
void Rotate(int x){
int y=fa[x],z=fa[y],ss=get(x);
if(!isRoot(y)) ch[z][y==ch[z][1]]=x;
ch[y][ss]=ch[x][!ss];fa[ch[x][!ss]]=y;
ch[x][!ss]=y;fa[y]=x;fa[x]=z;
PushUp(y);PushUp(x);
}
void Update(int x){
if(!isRoot(x)) Update(fa[x]);
PushDown(x);
}
void Splay(int x){
Update(x);
for(int f=fa[x];f=fa[x],!isRoot(x);Rotate(x)){
if(!isRoot(f)) Rotate(get(x)==get(f)?f:x);
}
}
int Access(int x,int c){
int p=0;
for(;x;p=x,x=fa[x]){
Splay(x);ch[x][1]=p;PushUp(x);
t1.upd(co[x],sz[p]-sz[x]);
t1.upd(c,sz[x]-sz[p]);
co[x]=c;
coltag[x]=c;
}
return p;
}
void MakeRoot(int x,int c){
x=Access(x,c);
swap(ch[x][0],ch[x][1]);
revtag[x]^=1;
}
int Askcol(int x){
Splay(x);
return co[x];
}
}t2;
int dpt[N],dfn[N],Tm,ST[19][N],mx[N];
void dfs(int x,int fa){
mx[x]=x;
t2.fa[x]=fa;
dfn[x]=++Tm;
ST[0][dfn[x]]=dpt[fa];
dpt[x]=dpt[fa]+1;
for(auto i:e[x]){
if(i==fa) continue;
dfs(i,x);
mx[x]=max(mx[x],mx[i]);
}
t2.co[x]=mx[x];
t1.upd(mx[x],1);
}
void initst(){
forup(i,0,17){
forup(j,1,n-(1<<(i+1))+1){
ST[i+1][j]=min(ST[i][j],ST[i][j+(1<<i)]);
}
}
}
int dis(int u,int v){
if(u==v) return 0;
int d1=dpt[u],d2=dpt[v];
u=dfn[u];v=dfn[v];
if(u>v) swap(u,v);
++u;
int len=31^__builtin_clz(v-u+1);
int d3=min(ST[len][u],ST[len][v-(1<<len)+1]);
return d1+d2-d3*2;
}
char str[10];
int mp[N<<1];
int pre;
signed main(){
n=read();m=read();
forup(i,1,n){
mp[i]=i;
}
forup(i,1,n-1){
int u=read(),v=read();
e[u].push_back(v);
e[v].push_back(u);
}
dfs(n,0);
pre=n;
initst();
forup(i,1,m){
scanf(" %s",str);
if(str[0]=='u'){
int v=read();
t2.MakeRoot(v,pre);
mp[n+i]=v;
pre=n+i;
}else if(str[0]=='w'){
int v=read();
int c=t2.Askcol(v);
printf("%d\n",t1.sum(c-1)+dis(mp[c],v)+1);
}else{
int u=read(),v=read();
int cu=t2.Askcol(u),cv=t2.Askcol(v);
if(cu==cv){
printf("%d\n",dis(mp[cu],u)<dis(mp[cv],v)?u:v);
}else{
printf("%d\n",cu<cv?u:v);
}
}
}
}
P6292 区间本质不同子串个数
考虑放到 SAM 上考虑。
容易发现对于一个询问 $[l,r]$，要求的就是在 $r$ 之前最后一次出现的左端点大于等于 $l$ 的字符串数量。
容易想到离线下来，用 LCT 维护最后一次出现（注意每次 $r$ 变大对应的一条 parent tree 上的链上最后一次出现的时间都会更新，那么就是一个链上染色），然后线段树维护左端点的区间加区间和即可。复杂度 $O(n\log^2 n)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5;
int n,m;
char str[N];
int tr[N][26],lnk[N],len[N],cntn,lst;
void Insert(int c){
int x=++cntn,p=lst;lst=x;
len[x]=len[p]+1;
while(p&&!tr[p][c]){
tr[p][c]=x;
p=lnk[p];
}
if(!p){
lnk[x]=1;
return;
}
int q=tr[p][c];
if(len[q]==len[p]+1){
lnk[x]=q;
return;
}else{
int _q=++cntn;
len[_q]=len[p]+1;
lnk[_q]=lnk[q];
lnk[x]=lnk[q]=_q;
forup(i,0,25) tr[_q][i]=tr[q][i];
while(p&&tr[p][c]==q){
tr[p][c]=_q;
p=lnk[p];
}
}
}
struct SegTree{
#define mid ((l+r)>>1)
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
i64 querysum[N<<1],mark[N<<1];
void PushUp(int id){
querysum[id]=querysum[id<<1]+querysum[id<<1|1];
}
void PushDown(int id,int l,int r){
mark[id<<1]+=mark[id];
mark[id<<1|1]+=mark[id];
querysum[id<<1]+=mark[id]*(mid-l+1);
querysum[id<<1|1]+=mark[id]*(r-mid);
mark[id]=0;
}
void Update(int L,int R,i64 X,int l=1,int r=n,int id=1){
if(L>R) return;
if(L<=l&&r<=R){
querysum[id]+=(r-l+1)*X;
mark[id]+=X;
return;
}
if(mark[id]) PushDown(id,l,r);
if(L<=mid) Update(L,R,X,lson);
if(mid< R) Update(L,R,X,rson);
PushUp(id);
}
i64 Query(int L,int R,int l=1,int r=n,int id=1){
if(L<=l&&r<=R){
return querysum[id];
}
if(mark[id]) PushDown(id,l,r);
i64 res=0;
if(L<=mid) res+=Query(L,R,lson);
if(mid< R) res+=Query(L,R,rson);
return res;
}
}t1;
struct LCT{
int ch[N][2],fa[N],co[N],mark[N];
#define get(x) (ch[fa[x]][1]==x)
#define isRoot(x) (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x)
void PushDown(int id){
if(mark[id]){
if(ch[id][0]){
co[ch[id][0]]=mark[id];
mark[ch[id][0]]=mark[id];
}
if(ch[id][1]){
co[ch[id][1]]=mark[id];
mark[ch[id][1]]=mark[id];
}
mark[id]=0;
}
}
void Rotate(int x){
int y=fa[x],z=fa[y],ss=get(x);
if(!isRoot(y)) ch[z][ch[z][1]==y]=x;
ch[y][ss]=ch[x][!ss];fa[ch[x][!ss]]=y;
ch[x][!ss]=y;fa[y]=x;fa[x]=z;
}
void Update(int x){
if(!isRoot(x)) Update(fa[x]);
PushDown(x);
}
void Splay(int x){
Update(x);
for(int f=fa[x];f=fa[x],!isRoot(x);Rotate(x)){
if(!isRoot(f)) Rotate(get(x)==get(f)?f:x);
}
}
void Access(int x,int c){
for(int p=0;x;p=x,x=fa[x]){
Splay(x);ch[x][1]=p;
if(co[x]) t1.Update(co[x]-len[x]+1,co[x]-len[fa[x]],-1);
co[x]=mark[x]=c;
t1.Update(c-len[x]+1,c-len[fa[x]],1);
}
}
}t2;
struct query{
int l,pos;
};
i64 ans[N];
vector<query> q[N];
signed main(){
scanf(" %s",str+1);
n=strlen(str+1);
cntn=lst=1;
lnk[1]=len[1]=0;
forup(i,1,n){
Insert(str[i]-'a');
}
forup(i,2,cntn){
t2.fa[i]=lnk[i];
}
m=read();
forup(i,1,m){
int l=read(),r=read();
q[r].push_back(query{l,i});
}
int p=1;
forup(i,1,n){
p=tr[p][str[i]-'a'];
t2.Access(p,i);
for(auto j:q[i]){
ans[j.pos]=t1.Query(j.l,i);
}
}
forup(i,1,m){
printf("%lld\n",ans[i]);
}
}
Gym-100800H Sunlight
妈的垃圾号爸只晓得抓 Gym 题。
简单题。
考虑分别找到 $x'
那么这个怎么求呢？这个可以单调栈啊，用单调栈维护一个凸包即可。
那么知道了 $x',y'$ 后应该怎么求答案呢？这个可以用 C++ 的 atan2 函数。atan2 函数引用时形如 atan2(y,x)，在 $x>0$ 时返回 $\arctan(\frac{y}{x})$（弧度制），另外 $\pi$ 最好用 acos(-1) 计算。
复杂度 $O(n)$，带浮点计算的常数。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=2e5+5,inf=0x3f3f3f3f;
i64 n;
double ans[N],pi=acos(-1),u=12/pi;
struct Node{
i64 x,y,pos;
}s[N];
bool slp(Node a,Node b,Node c){
return (b.y-a.y)*(c.x-b.x)>(c.y-b.y)*(b.x-a.x);
}
signed main(){
n=read();
forup(i,1,n){
s[i].x=read();s[i].y=read();s[i].pos=i;
ans[i]=12;
}
sort(s+1,s+n+1,[&](Node a,Node b){
return a.x<b.x;
});
vector<Node> stk;
forup(i,1,n){
if(stk.empty()){
stk.push_back(s[i]);
continue;
}
while(stk.size()>1&&!slp(stk[stk.size()-2],stk[stk.size()-1],s[i])) stk.pop_back();
Node nw=stk.back();
if(nw.y>s[i].y){
ans[s[i].pos]-=u*atan2(nw.y-s[i].y,s[i].x-nw.x);
}
stk.push_back(s[i]);
}
stk.clear();
fordown(i,n,1){
if(stk.empty()){
stk.push_back(s[i]);
continue;
}
while(stk.size()>1&&!slp(s[i],stk[stk.size()-1],stk[stk.size()-2])) stk.pop_back();
Node nw=stk.back();
if(nw.y>s[i].y){
ans[s[i].pos]-=u*atan2(nw.y-s[i].y,nw.x-s[i].x);
}
stk.push_back(s[i]);
}
forup(i,1,n){
printf("%.6lf\n",ans[i]);
}
}
Gym-101201L Windy Path
简单题。
题意是平面上有若干个点，保证没有三点共线。你需要规划一条路径经过每个点，但是规定每次拐弯是顺时针还是逆时针。
思路是每一步都保证下一步能到达任意点。这个其实很简单啊，最开始找一个边凸包上的点，然后每次考虑下一次拐弯是左拐还是右拐，如果是左拐就走剩下点的凸包最右边（按角度来算）的点，否则走最左边即可。
复杂度可以做到 $O(n^2)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=55,inf=0x3f3f3f3f;
int n;
struct Point{
int x,y;
}s[N];
int nw;
int cj(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
char str[N];
int vis[N];
vector<int> ans;
signed main(){
n=read();
forup(i,1,n){
s[i].x=read();s[i].y=read();
if(i==1||s[i].x<s[nw].x){
nw=i;
}
}
scanf(" %s",str+1);
vis[nw]=1;
ans.push_back(nw);
forup(i,1,n-2){
if(str[i]=='L'){
int mx=0;
forup(j,1,n){
if(vis[j]) continue;
if(mx==0){
mx=j;
}else{
Point pa=Point{s[mx].x-s[nw].x,s[mx].y-s[nw].y},pb={s[j].x-s[nw].x,s[j].y-s[nw].y};
if(cj(pa,pb)<0){
mx=j;
}
}
}
nw=mx;
vis[nw]=1;
}else{
int mx=0;
forup(j,1,n){
if(vis[j]) continue;
if(mx==0){
mx=j;
}else{
Point pa=Point{s[mx].x-s[nw].x,s[mx].y-s[nw].y},pb={s[j].x-s[nw].x,s[j].y-s[nw].y};
if(cj(pa,pb)>0){
mx=j;
}
}
}
nw=mx;
vis[nw]=1;
}
ans.push_back(nw);
}
forup(i,1,n){
if(!vis[i]){
ans.push_back(i);
}
}
for(auto i:ans){
printf("%d ",i);
}
}
Gym-101806U United States of Eurasia
最小化最大值，考虑二分。
那么二分答案后考虑如何 check。容易想到一个贪心，每次在最远点距不超过 $mid$ 的情况下尽可能远地拓展。那么这个怎么做呢？容易想到二分 $+$ 旋转卡壳。
但是这个 check 直接做复杂度不太对啊，大概是 $O(NK\log N)$ 的，考虑优化。这里有一个 trick，倍增优化二分。
具体来说，先尝试区间长度为 $2^0,2^1,2^2\dots$，一直找到第一个最远点对超过 $mid$ 的区间长度为 $2^k$，那么答案必定在 $[2^{k-1},2^k)$ 中产生。这一部分复杂度是 $O(\text{答案区间长度})$ 的。然后在这一部分里面二分，复杂度是 $O(\text{答案区间长度}\times k)$ 的。这样总复杂度就是 $O(N\log N)$，然后就对了。
参考代码
代码很屎。
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const i64 N=250005;
int n,m;
struct Point{
int x,y;
bool operator ==(Point r){
return x==r.x&&y==r.y;
}
}s[N];
bool slp(Point a,Point b,Point c){
return 1ll*(b.y-a.y)*(c.x-b.x)<1ll*(c.y-b.y)*(b.x-a.x);
}
i64 cj(Point a,Point b){
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
vector<Point> vec;
i64 dist(Point a,Point b){
return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y);
}
void Gettb(int l,int r){
vec.clear();
vector<Point> v;
auto work=[&](int n){
vector<Point> stk;
forup(i,0,n-1){
if(stk.empty()) stk.push_back(v[i]);
while(stk.size()>1&&!slp(stk[stk.size()-2],stk[stk.size()-1],v[i])) stk.pop_back();
stk.push_back(v[i]);
}
i64 sz=stk.size()-1;
forup(i,1,sz){
vec.push_back(stk[i]);
}
};
forup(i,l,r){
v.push_back(s[i]);
}
work(v.size());
reverse(v.begin(),v.end());
work(v.size());
vec.push_back(vec[0]);
}
int chk(int i,int x){
Point pa=Point{vec[i].x-vec[x].x,vec[i].y-vec[x].y},pb=Point{vec[i+1].x-vec[x].x,vec[i+1].y-vec[x].y};
i64 G=abs(cj(pa,pb));
x=(x+1)%vec.size();
pa=Point{vec[i].x-vec[x].x,vec[i].y-vec[x].y},pb=Point{vec[i+1].x-vec[x].x,vec[i+1].y-vec[x].y};
i64 G2=abs(cj(pa,pb));
if(G2==G) return -1;
return G2>G;
}
i64 solve(int l,int r){
Gettb(l,r);
if(vec.size()==2) return 0;
int sz=vec.size()-1,po=0;
i64 ans=0,mx=0;
forup(i,0,sz){
Point pa=Point{vec[0].x-vec[i].x,vec[0].y-vec[i].y},pb=Point{vec[1].x-vec[i].x,vec[1].y-vec[i].y};
i64 G=abs(cj(pa,pb));
if(G>mx){
mx=G;
po=i;
}
}
forup(i,0,sz-1){
while(chk(i,po)==1){
po=(po+1)%vec.size();
}
ans=max(ans,dist(vec[i],vec[po]));
ans=max(ans,dist(vec[i+1],vec[po]));
if(chk(i,po)==-1){
po=(po+1)%vec.size();
ans=max(ans,dist(vec[i],vec[po]));
ans=max(ans,dist(vec[i+1],vec[po]));
}
}
return ans;
}
int mp[N],sz;
i64 sv[N][19];
i64 f(int i,int j){
if(sv[i][j]) return sv[i][j];
return sv[i][j]=solve(mp[i],mp[min(i+(1<<j),sz+1)]-1);
}
bool Chk(i64 aa){
int p=1,k=0;
while(p<=sz){
int ll=0,rr=0,mm;
forup(i,1,18){
if(f(p,i)>aa){
ll=min(p+(1<<(i-1))-1,sz);rr=min(p+(1<<i)-1,sz);
break;
}
if(p+(1<<i)>sz) break;
}
if(ll==0&&rr==0){
++k;
return k<=m;
}
while(ll<rr){
mm=(ll+rr+1)>>1;
if(solve(mp[p],mp[mm+1]-1)<=aa) ll=mm;
else rr=mm-1;
}
++k;p=ll+1;
if(k>m) return false;
if(k==m&&p<=n) return false;
}
return k<=m;
}
signed main(){
n=read();m=read();
forup(i,1,n){
s[i].x=read();s[i].y=read();
}
sort(s+1,s+n+1,[&](Point a,Point b){
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
});
sz=0;
n=unique(s+1,s+n+1)-s-1;
forup(i,1,n){
if(i==1||s[i].x!=s[i-1].x){
++sz;
mp[sz]=i;
}
}
mp[sz+1]=n+1;
i64 mn=0;
forup(i,1,sz){
mn=max(mn,solve(mp[i],mp[i+1]-1));
}
i64 ll=mn,rr=solve(1,n),mm;
while(ll<rr){
mm=(ll+rr)>>1;
if(Chk(mm)) rr=mm;
else ll=mm+1;
}
printf("%lld\n",ll);
}
Gym-100960 The Jedi Killer
最解析几何的一集。
特判三点共线后，枚举哪两点共线，另一点用垂线去交。
注意共线可能是 $L_g$ 的那条也可能是 $L_m$ 的那条。注意一次函数斜率可能不存在，这时候可以微小扰动或者像我一样特判。（但是用向量就没有问题了）
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);i++)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using db=long double;
#define gc getchar()
inline i64 read(){
i64 x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const db eps=1e-6;
i64 t;
struct Point{
db x,y;
}s[3];
db cj(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
i64 lg,lm;
bool eql(db a,db b){
return fabs(a-b)<=eps;
}
db dis(Point a,Point b){
return sqrtl((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool work(){
if(!eql(s[0].x,s[1].x)&&!eql(s[0].y,s[1].y)){
db k1=(s[1].y-s[0].y)/(s[1].x-s[0].x),b1=s[0].y-s[0].x*k1;
db k2=-1/k1,b2=s[2].y-s[2].x*k2;
db x=(b2-b1)/(k1-k2),y=k1*x+b1;
Point o=Point{x,y};
db d1=dis(s[0],o),d2=dis(s[1],o),d3=dis(s[2],o);
return (d1-eps<=lg&&d2-eps<=lg&&d3-eps<=lm)||((s[0].x-x)*(s[1].x-x)+(s[0].y-y)*(s[1].y-y)>=-eps&&d1-eps<=lm&&d2-eps<=lm&&d3-eps<=lg);
}else{
if(eql(s[0].x,s[1].x)){
db d1=fabs(s[0].y-s[2].y),d2=fabs(s[1].y-s[2].y),d3=fabs(s[0].x-s[2].x);
return (d1-eps<=lg&&d2-eps<=lg&&d3-eps<=lm)||((s[0].y-s[2].y)*(s[1].y-s[2].y)>=-eps&&d1-eps<=lm&&d2-eps<=lm&&d3-eps<=lg);
}else{
db d1=fabs(s[0].x-s[2].x),d2=fabs(s[1].x-s[2].x),d3=fabs(s[0].y-s[2].y);
return (d1-eps<=lg&&d2-eps<=lg&&d3-eps<=lm)||((s[0].x-s[2].x)*(s[1].x-s[2].x)>=-eps&&d1-eps<=lm&&d2-eps<=lm&&d3-eps<=lg);
}
}
}
void solve(){
lm=read(),lg=read();
forup(i,0,2){
scanf(" %Lf %Lf",&s[i].x,&s[i].y);
}
if(eql(cj(Point{s[1].x-s[0].x,s[1].y-s[0].y},Point{s[2].x-s[0].x,s[2].y-s[0].y}),0)){
db len=max({dis(s[0],s[1]),dis(s[1],s[2]),dis(s[0],s[2])});
if(lm>=len||lg*2>=len){
puts("YES");
}else{
puts("NO");
}
return;
}
if(work()) return puts("YES"),void();
Point tmp=s[0];
s[0]=s[1];s[1]=s[2];
s[2]=tmp;
if(work()) return puts("YES"),void();
tmp=s[0];
s[0]=s[1];s[1]=s[2];
s[2]=tmp;
if(work()) return puts("YES"),void();
puts("NO");
}
signed main(){
t=read();
while(t--){
solve();
}
}
Gym-101237J Dividing Area
考虑加边相当于是分裂平面。而分裂是不好做的，所以考虑倒过来合并平面。
另外观察求多边形面积的方法：每条边两个向量叉积算有向面积求和。容易发现每条边是独立的。那么可以把每条边视为正向和反向两条边，然后维护边的并查集，删边就相当于把一条边两个方向并起来。然后面积就是对应并查集每条边的贡献和。如果是负数或者 $0$ 说明不是封闭部分。
那么剩下的难点在于如何初始化。考虑对每个点的出边极角排序，那么显然相邻的两条边会处于同一集合，且是较前者的正向边与较后者的反向边（因为要求按逆时针计算）。这里写的丑时会有精度问题，考虑当 atan2 的差小于 $eps$ 的时候用叉积求谁先谁后。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
#define y1 y114514
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=2e5+5,M=1e6+6;
int n,m,x[N],y[N],cnte=1;
struct query{
int op,a,b;
}s[M];
struct line{
int x1,y1,x2,y2;
}L[M*2];
i64 sz[M*2];
int fa[M*2];
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
void Merge(int u,int v){
int fu=getfa(u),fv=getfa(v);
if(fu==fv) return;
sz[fv]+=sz[fu];
fa[fu]=fv;
}
vector<int> e[N];
map<pii,int> sv;
i64 cross(line a){
return 1ll*a.x1*a.y2-1ll*a.x2*a.y1;
}
int New(int x1,int y1,int x2,int y2){
int nw=++cnte;
L[nw]=line{x1,y1,x2,y2};
fa[nw]=nw;sz[nw]=cross(L[nw]);
return nw;
}
vector<i64> ans;
signed main(){
n=read();
forup(i,1,n){
x[i]=read();y[i]=read();
}
m=read();
forup(i,1,m){
int op=read(),a=read()+1,b=read()+1;
s[i]=query{op,a,b};
if(op==1){
int ee=New(x[a],y[a],x[b],y[b]);
e[a].push_back(ee);
sv[mkp(a,b)]=ee;
ee=New(x[b],y[b],x[a],y[a]);
e[b].push_back(ee);
sv[mkp(b,a)]=ee;
}
}
forup(i,1,n){
sort(e[i].begin(),e[i].end(),[&](int u,int v){
line a=L[u],b=L[v];
return fabs(atan2(a.y2-a.y1,a.x2-a.x1)-atan2(b.y2-b.y1,b.x2-b.x1))>1e-6?atan2(a.y2-a.y1,a.x2-a.x1)<atan2(b.y2-b.y1,b.x2-b.x1):cross(line{a.x2-a.x1,a.y2-a.y1,b.x2-b.x1,b.y2-b.y1})>0;
});
int sz=e[i].size();
forup(u,0,sz-1){
int v=(u+1)%sz;
Merge(e[i][u],e[i][v]^1);
}
}
fordown(i,m,1){
if(s[i].op==0){
i64 res=sz[getfa(sv[mkp(s[i].a,s[i].b)])];
if(res<=0){
ans.push_back(-1);
}else{
ans.push_back(res);
}
}else{
int p=sv[mkp(s[i].a,s[i].b)];
Merge(p,p^1);
}
}
reverse(ans.begin(),ans.end());
for(auto i:ans){
printf("%lld\n",i);
}
}