P9744 「KDOI-06-S」消除序列
我们可以很容易发现操作 1 只可能使用一次。
先考虑序列固定的情况下的做法。
我们设 \(f_i\) 表示 \(1\sim i\) 用操作 1，\(i+1\sim n\) 不用的最小值。（\(i\) 可以取 \(0\)，表示不用操作 1）
对于前半部分，先推平，\(a_i\) 的代价，然后将要求是 \(1\) 的部分加上对应的 \(c\)；后半部分，将不是 \(1\) 的部分加上对应的 \(b\)（因为后半部分初始默认都是 \(1\)）。
形式化：\(a_0=0,f_i=a_i+\sum_{j=1}^i[st_j=1]c_j+\sum_{j=i+1}^n[st_j=0]b_j\)
按照这种方式模拟，就可以得到 70 分。
我们先求解出 \(st\) 全部是 \(0\) 的 \(f\)，然后考虑对于每次询问如何做。
可以将要求是 \(1\) 的位置相当于修改为 \(1\)，然后求解一遍，最后修改回来。
发现一次修改，对于 \(i\in[0,x-1],f_i\leftarrow f_i-b_x;i\in[x,n],f_i\leftarrow f_i+c_x\)
发现这个可以用线段树维护区间修改，区间查询最小值。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=500010,M=4*N;
int n,b[N],c[N],num[20],tmp[N];
ll v[M],f[M],a[N];
int l[M],r[M];
#define ls p<<1
#define rs p<<1|1
#define up v[p]=min(v[ls],v[rs])
void read(int &x){
x=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
}
void read(ll &x){
x=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
}
void write(ll x,char fg='\n'){
if(!x){
putchar('0');
putchar(fg);
return;
}
int cur=0;
while(x)num[++cur]=x%10+'0',x/=10;
for(int i=cur;i;--i)putchar(num[i]);
putchar(fg);
}
void build(int p,int L,int R){
l[p]=L,r[p]=R;
if(L==R){
v[p]=a[L];
return;
}
int mid=L+R>>1;
build(ls,L,mid),build(rs,mid+1,R);
up;
}
#define ch(p,val) v[p]+=val,f[p]+=val;
void down(int p){
ll &val=f[p];
if(f[p]){
ch(ls,val);
ch(rs,val);
val=0;
}
}
void update(int p,int L,int R,int val){
if(L<=l[p]&&r[p]<=R){
ch(p,val);
return;
}
down(p);
int mid=l[p]+r[p]>>1;
if(L<=mid)update(ls,L,R,val);
if(R>mid)update(rs,L,R,val);
up;
}
int main(){
read(n);
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<=n;++i)read(b[i]);
for(int i=1;i<=n;++i)read(c[i]);
ll tm=0;
for(int i=n-1;~i;--i){
tm+=b[i+1];
a[i]+=tm;
}
// for(int i=0;i<=n;++i)write(a[i],' ');
// puts("");
build(1,0,n);
int q;
read(q);
while(q--){
int m;
read(m);
// cout<<v[1]<<'\n';
for(int i=1;i<=m;++i){
int x;
read(tmp[i]);
x=tmp[i];
update(1,0,x-1,-b[x]);
// cout<<0<<' '<<x-1<<' '<<-b[x]<<'\n';
update(1,x,n,c[x]);
// cout<<x<<' '<<n<<' '<<c[x]<<'\n';
}
// cout<<v[1]<<'\n';
write(v[1]);
for(int i=1;i<=m;++i){
int x=tmp[i];
update(1,0,x-1,b[x]);
update(1,x,n,-c[x]);
}
}
return 0;
}