CF1887C Minimum Array
樱雪喵
·
·
题解
被 A2 卡没时间了 /oh
Description
给一个长度为 n 的初始序列 a 和 q 次操作。每次操作形如给 a_l\sim a_r 的值加上 k。
依次进行这些操作，求过程中得到过字典序最小的序列。
## Solution 1
考虑依次进行每个操作，维护当前能使答案字典序最小的**操作编号** $ans$。
只考虑从上一个 $ans$ 到当前时刻的操作，设它们操作后形成的序列为 $b$。那么当前的实际序列就是 $[1,ans]$ 的实际序列与 $b$ 数组对应位相加后的结果。
当前序列比 $[1,ans]$ 字典序更小的充要条件是 $b$ 中第一个不为 $0$ 的位置的值 $<0$，证明是显然的。每次修改后判断，满足这个条件就更新 $ans$，并清零 $b$ 数组。
也就是说我们只需要一个数据结构支持区间加、求第一个不为 $0$ 的位置、单点求值。
直接上线段树是可做的。不过发现第一个不为 $0$ 的位置只能是某个 $l_i$ 或 $r_i+1$，所以把这些点塞进 `set` 里暴力判断即可，区间加用树状数组维护。
## Solution 2
看了下官方题解。
我们直接在差分数组上考虑这个问题，修改变成了单点，更新答案还是求第一个不为 $0$ 的位置。这样就不用写树状数组了。
```cpp
#define int long long
const int N=5e5+5,inf=1e9;
int t,n,a[N];
struct node{int l,r,k;} q[N];
struct BIT
{
int tr[N];
il void modify(int x,int k) {for(;x<=n;x+=x&(-x)) tr[x]+=k;}
il void add(int l,int r,int k) {modify(l,k),modify(r+1,-k);}
il int query(int x) {int res=0;for(;x;x-=x&(-x)) res+=tr[x];return res;}
}tr;
int ans;
signed main()
{
int T=read();
while(T--)
{
n=read(); ans=0;
for(int i=1;i<=n;i++) a[i]=read(),tr.tr[i]=0;
t=read(); set<int> st;
for(int i=1;i<=t;i++) q[i].l=read(),q[i].r=read(),q[i].k=read();
for(int i=1;i<=t;i++)
{
tr.add(q[i].l,q[i].r,q[i].k);
st.insert(q[i].l),st.insert(q[i].r+1);
while(st.size()&&!tr.query(*st.begin())) st.erase(st.begin());
if(!st.empty()&&tr.query(*st.begin())<0)
{
for(int j=i;j>ans;j--) tr.add(q[j].l,q[j].r,-q[j].k);
ans=i,st.clear();
}
}
for(int i=1;i<=n;i++) tr.tr[i]=0;
for(int i=1;i<=n;i++) tr.modify(i,a[i]-a[i-1]);
for(int i=1;i<=ans;i++) tr.add(q[i].l,q[i].r,q[i].k);
for(int i=1;i<=n;i++) printf("%lld ",tr.query(i));
printf("\n");
}
}
```