首页 > 分享 > 【高手训练】【线段树】栈的维护

【高手训练】【线段树】栈的维护

萌宠菠菠乐园
2024-10-24 10:01

Weed

Time Limit: 20 Sec Memory Limit: 512 MB

Description

　　从前有个栈，一开始是空的。
　　你写下了 m 个操作，每个操作形如 k v :
　　　　若 k = 0，代表往栈顶加入一个数 v
　　　　若 k = 1，则代表从栈顶弹出 v 个数，如果栈中的元素少于 v 个，则全部弹出。
　　接着你又进行了 q 次修改，每次你会选择一个操作，并且修改它的两个参数。
　　在每次修改后，你都要求出如果依次执行这些操作，最后栈中剩下的元素之和。

Input

　　第一行两个正整数 m,q，分别表示操作数和修改次数。
　　接下来 m 行，每行两个整数 k,v，代表一个操作。
　　接下来 q 行，每行三个正整数 c,k,v，表示将第 c 个操作的参数修改为 k 和 v。

Output

　　输出 q 行，每行一个整数，代表依次执行所有操作后栈中剩下的元素之和。

Sample Input

　　5 2
　　0 3
　　0 2
　　0 3
　　1 1
　　0 5
　　1 0 3
　　1 0 1

Sample Output

　　10
　　8

HINT

　　m,q ≤ 2×1e5, v ≤ 1e4

这个嘛。。。
其实一看觉得不像是线段树
但是这又是修改，又是查询的awa
不找他找谁呢awa

如果想要按照线段树的方法来搞的话，不考虑数据的其他性质，可以发现，我们能维护的只有他之前给的操作。。。

因为这个操作其实是就是答案的序列。。
而且题目的修改也是针对这个东西的。

所以我觉得应该就是要维护这个东西的awa

get到了新的线段树维护方法awa，妙啊

进入正题

以操作顺序为下标，建立一棵线段树

发现题目中的修改的区间影响的范围非常大，是从这个点开始，一直到结尾的
考虑修改的方法。

在建树是，我们上传的东西其实是假设没有修改操作时候的栈的答案。
有以下几点，是要记录的

　　1.一个区间中，又增加有删除的数字，是没有意义的，可以忽略

　　2.维护区间和

　　3.除了被抵消的数，还需要删除的数　　这些操作只能有前面的数来补

　　4.除了被抵消的数，还需要添加的数　　这些操作只能被后面的操作给删掉　

这些其实就是我们应该考虑的全部的情况了。

我们最终的目标就是区间累加和

然后就是维护的问题awa

剩下就是维护的问题。

这两个式子，第一个是最终删除的数，第二个是最终添加的数。

合并时，右区间的和是不会受到影响的，但是因为右区间的del(删除的数)，左区间的一些数可能会被删去。

于是这么一个问题，对于操作区间p，之后要删x个数，删完以后这个区间的和是多少。即为Cal(p,x)

如果add_p<=x显然这个区间被删完了，就是0

如果add_rs>=x，只要删右区间的数就好了，问题转化为一个子问题

否则右区间的数要全部删掉，然后再在左区间删。

然后就没了awa

Code

#include<bits/stdc++.h> #define ll long long using namespace std; int n,m,q,a[300001]; struct edge { int sum,del,add,l,r; }t[8000001]; inline ll read() { char c=getchar();ll a=0,b=1; for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1; for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48; return a*b; } int Cal(int q,int x) { if(!x)return t[q].sum; if(x>=t[q].add)return 0; if(t[q*2+1].add>=x) return t[q].sum-t[q*2+1].sum+Cal(q*2+1,x); return Cal(q*2,x-t[q*2+1].add+t[q*2+1].del); } void push_up(int q) { t[q].add=t[q*2+1].add+max(t[q*2].add-t[q*2+1].del,0); t[q].del=t[q*2].del+max(t[q*2+1].del-t[q*2].add,0); t[q].sum=t[q*2+1].sum+Cal(q*2,t[q*2+1].del); } void build(int q,int l,int r) { t[q].l=l,t[q].r=r; if(l==r) { if(a[l]>0)t[q].sum=a[l],t[q].add=1; else t[q].del=-a[l]; return; } int mid=l+r>>1; build(q*2,l,mid); build(q*2+1,mid+1,r); push_up(q); } void Modiffy(int q,int x,int k,int v) { if(t[q].l==x&&t[q].r==x) { t[q].del=t[q].sum=t[q].add=0; if(k==0) { t[q].add=1;t[q].sum=v; } else { t[q].del=v; } return ; } int mid=(t[q].l+t[q].r)>>1; if(x<=mid)Modiffy(q*2,x,k,v); else Modiffy(q*2+1,x,k,v); push_up(q); } int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); n=read();q=read(); for(int i=1;i<=n;i++) { int op=read(),v=read(); if(op==0)a[i]=v; else a[i]=-v; } build(1,1,n); for(int i=1;i<=q;i++) { int c=read(),k=read(),v=read(); Modiffy(1,c,k,v); cout<<t[1].sum<<endl; } return 0; }

调了一个小时

痛苦万分。。。
线段树真的是一个字符写错了就炸了。。。

唉

这道题主要是给我了一种新的建树方法

其实线段树的统计和更改操作可以通过一定的方法来适应题目，解决问题。