栈(stack)

题意

九条可怜最近学习了一个叫做单调栈的数据结构。它和栈的不同点在于,往栈顶加入一个数$x$的时候会把栈中所有小于等于$x$的数都弹出再加入,从而保证栈中的所有元素都是有序的。
例如单调栈$[5, 4, 2, 1]$在加入$3$后会先弹出$1$和$2$,再加入$3$变成$[5,4,3]$。
现在可怜有$n$个单调栈,编号从$1$到$n$,初始全为空。接着可怜进行了若干次操作:

  • 1 l r x,表示往第$l$到第$r$个单调栈内加入数$x$。
  • 2 k,表示询问第$k$个单调栈内所有数的和。

维护这些操作对可怜来说有点难,于是她向你寻求帮助,你能帮帮她吗。

题解

这道题的模型转化之神奇……真是让人感叹啊……
首先把询问离线掉,然后神奇的模型转化就来了:化每一个单调栈为时间线。即对于每一次区间$[l,r]$加上一个数,相当于在第$l$秒往结构中加入一个数,在第$r+1$秒前将其删除。而询问第$i$个单调栈内所有数的和,相当于在第$i$秒查询结构内满足单调栈的性质的所有数的和。
接下来还要解决满足单调栈性质的问题,不难发现,此时这个问题就和楼房重建差不多啦。直接改改套上板子就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=2e5+10;
struct node{
int l,r,x,id;
};
struct point{
int srt,id;
};
vector <int> del[maxn];
vector <node> add[maxn];
vector <point> query[maxn];
ll Seg[maxn<<2],Ans[maxn<<2],ans[maxn],Maxval,Finalans;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline ll Update(int h,int l,int r,int maxval){
if(l==r)return Seg[h]>maxval?Seg[h]:0;
int mid=(l+r)>>1;
if(Seg[h<<1|1]<=maxval)return Update(h<<1,l,mid,maxval);
else return Update(h<<1|1,mid+1,r,maxval)+Ans[h]-Ans[h<<1|1];
}
inline void Modify(int h,int l,int r,int pos,int curindex){
if(l==r){
Seg[h]=curindex;
Ans[h]=curindex;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)Modify(h<<1,l,mid,pos,curindex);
else Modify(h<<1|1,mid+1,r,pos,curindex);
Seg[h]=max(Seg[h<<1],Seg[h<<1|1]);
Ans[h]=Ans[h<<1|1]+Update(h<<1,l,mid,Seg[h<<1|1]);
}
inline void GetAns(int h,int l,int r,int L,int R){
if(L<=l && r<=R){
Finalans+=Update(h,l,r,Maxval);
Maxval=max(Maxval,Seg[h]);
return;
}
int mid=(l+r)>>1;
if(R>mid)GetAns(h<<1|1,mid+1,r,L,R);
if(L<=mid)GetAns(h<<1,l,mid,L,R);
}
int main(){
int i,j,m,n;
freopen("stack.in","r",stdin);
freopen("stack.out","w",stdout);
n=read();m=read();
int cntq=0;
for(i=1;i<=m;i++){
int opt=read();
if(opt==1){
int l,r,x;
l=read();r=read();x=read();
add[l].push_back((node){l,r,x,i});
}
else{
int pos=read();
query[pos].push_back((point){++cntq,i});
}
}
int size;
for(i=1;i<=n;i++){
size=add[i].size();
for(j=0;j<size;j++){
Modify(1,1,n,add[i][j].id,add[i][j].x);
del[add[i][j].r+1].push_back(add[i][j].id);
}
size=del[i].size();
for(j=0;j<size;j++)Modify(1,1,n,del[i][j],0);
size=query[i].size();
for(j=0;j<size;j++){
Maxval=Finalans=0;
GetAns(1,1,n,1,query[i][j].id);
ans[query[i][j].srt]=Finalans;
}
}
for(i=1;i<=cntq;i++)printf("%lld\n",ans[i]);
return 0;
}