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(删除的数)，左区间的一些数可能会被删去。
如果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; }
调了一个小时
痛苦万分。。。
线段树真的是一个字符写错了就炸了。。。
唉
这道题主要是给我了一种新的建树方法
其实线段树的统计和更改操作可以通过一定的方法来适应题目，解决问题。
原文链接: https://www.cnblogs.com/HLZZPawa/p/13210387.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/360590
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
