BZOJ2158 : Crash 的旅行计划
计划 旅行 Crash
2023-09-11 14:15:05 时间
A类数据：
$n,q\leq1000$
修改：$O(1)$直接改
查询：$O(n)$BFS
B类数据：
$n,q\leq100000$,保证是一条链
用线段树维护区间最大前缀、后缀和
修改：$O(\log n)$
查询：答案为max([1,x]的最大后缀和,[x,n]的最大前缀和)，$O(\log n)$
C类数据：
$n,q\leq100000$,保证以1为根时树高不超过40
设val[x]为从x向下走的最大和，val[x]=max(val[son[x]],0)+a[x]
每个点维护一棵平衡树，平衡树里每个节点存孩子id以及该孩子的val
预处理：$O(n\log n)$
修改：修改a[x]，然后从x开始把它的所有父亲都修改掉，$O(d\log n)$
查询：从x开始往上走，设sum[x]为到x时的总和(包括x)，ans=max(sum[x]+x平衡树中不是从之前儿子走过来的最大值)，$O(d\log n)$
总时间复杂度：$O((n+qd)\log n)$
#include<cstdio>
#include<set>
#include<algorithm>
#define P make_pair
#define T pair<int,int>
#define N 100010
#define M 200010
using namespace std;
struct qq{int k,x,y;}op[N];
int n,m;
int a[N],g[N],nxt[N<<1],v[N<<1],ed;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
namespace subtask1{
int q[N],h,t,vis[N],sum[N];
inline int cal(int x){
int ans=a[x],i;
for(i=1;i<=n;i++)vis[i]=0;
q[h=t=1]=x;vis[x]=1;sum[x]=a[x];
while(h<=t)for(i=g[x=q[h++]];i;i=nxt[i])if(!vis[v[i]])vis[q[++t]=v[i]]=1,ans=max(ans,sum[v[i]]=sum[x]+a[v[i]]);
return ans;
}
inline void work(){
for(int i=1;i<m;i++)if(op[i].k)a[op[i].x]=op[i].y;
else printf("%d\n",cal(op[i].x));
}
}
namespace subtask2{
struct msg{int ml,mr,sum;msg(){ml=mr=sum=0;}msg(int x){ml=mr=sum=x;}
inline msg operator+(const msg b){
msg c;
c.sum=sum+b.sum;
c.ml=max(ml,sum+b.ml);
c.mr=max(b.mr,b.sum+mr);
return c;
}
}val[M];
int l[M],r[M],tot;
void build(int c,int d){
int x=++tot;
if(c==d){val[x]=msg(a[c]);return;}
int mid=(c+d)>>1;
l[x]=tot+1;build(c,mid);
r[x]=tot+1;build(mid+1,d);
val[x]=val[l[x]]+val[r[x]];
}
void change(int x,int a,int b,int c,int p){
if(a==b){val[x]=msg(p);return;}
int mid=(a+b)>>1;
if(c<=mid)change(l[x],a,mid,c,p);else change(r[x],mid+1,b,c,p);
val[x]=val[l[x]]+val[r[x]];
}
msg ask(int x,int a,int b,int c,int d){
if(c<=a&&b<=d)return val[x];
int mid=(a+b)>>1;
if(d<=mid)return ask(l[x],a,mid,c,d);
if(c>mid)return ask(r[x],mid+1,b,c,d);
return ask(l[x],a,mid,c,d)+ask(r[x],mid+1,b,c,d);
}
inline void work(){
build(1,n);
for(int i=1;i<m;i++)if(op[i].k)change(1,1,n,op[i].x,op[i].y);
else printf("%d\n",max(ask(1,1,n,1,op[i].x).mr,ask(1,1,n,op[i].x,n).ml));
}
}
namespace subtask3{
int f[N],val[N];
set<T,greater<T> >b[N];
void dfs(int x,int pre){
f[x]=pre;b[x].insert(P(0,0));
for(int i=g[x];i;i=nxt[i])if(v[i]!=pre)dfs(v[i],x),b[x].insert(P(val[v[i]],v[i]));
val[x]=b[x].begin()->first+a[x];
}
inline void change(int x,int p){
int old=val[x],y=x;
a[x]=p;
val[x]=b[x].begin()->first+a[x];
while(f[x]){
b[f[x]].erase(P(old,y));
b[f[x]].insert(P(val[y],y));
old=val[f[x]],y=f[x];
val[f[x]]=b[f[x]].begin()->first+a[f[x]];
x=f[x];
}
}
inline int ask(int x){
int ans=val[x],sum=a[x],y=x;
x=f[x];
while(x){
sum+=a[x];
b[x].erase(P(val[y],y));
ans=max(ans,sum+b[x].begin()->first);
b[x].insert(P(val[y],y));
y=x;
x=f[x];
}
return ans;
}
inline void work(){
dfs(1,0);
for(int i=1;i<m;i++)if(op[i].k)change(op[i].x,op[i].y);
else printf("%d\n",ask(op[i].x));
}
}
int main(){
char c;int L,now,tmp,A,B,Q,i;
scanf("%c%d%d%d%d%d%d%d",&c,&n,&m,&L,&now,&A,&B,&Q);
for(i=1;i<=n;i++){
now=(now*A+B)%Q,tmp=now%10000;
now=(now*A+B)%Q;
if(now*2<Q)tmp*=-1;
a[i]=tmp;
}
for(i=1;i<n;i++){
now=(now*A+B)%Q;
tmp=(i<L)?i:L;
add(i-now%tmp,i+1);add(i+1,i-now%tmp);
}
for(i=1;i<m;i++){
now=(now*A+B)%Q;
if(now*3<Q){
now=(now*A+B)%Q;
op[i].x=now%n+1;
}else{
now=(now*A+B)%Q,tmp=now%10000;
now=(now*A+B)%Q;
if(now*2<Q)tmp*=-1;
now=(now*A+B)%Q;
op[i].k=1,op[i].x=now%n+1,op[i].y=tmp;
}
}
if(c=='A')subtask1::work();
if(c=='B')subtask2::work();
if(c=='C')subtask3::work();
return 0;
}