Zbox loves stack

题意

有 \(n\) 个栈，\(q\) 次操作，\(3\) 种操作。
1.\([l,r]\) 之间的栈全部加入一个数 \(k\)。
2.\([l,r]\) 之间的栈全部弹出栈顶。
3.第 \(s\) 个栈中的第 \(k\) 个元素，栈顶为第一个元素，没有则输出 Error。
\(n \leq 10^6,q \leq 10^5\)

题解

考试的时候想到了树套树的写法，但是因为不会可持久化平衡树寄掉了。
实际上是有 \(O(qlogn)\) 的写法的。
直接在线写标记下传感觉很难，所以考虑离线。

我们将先考虑我们如果知道一个栈的操作序列，将插入看做 \(1\)，删除看做 \(-1\)。
显然第 \(k\) 个元素就是最后一个后缀和为 \(k\) 的位置。

我们要怎么知道一个栈的操作序列？
用扫描线的方法把删除，添加和询问都挂在栈上,从后往前扫描。

光挂到栈上不行，还要知道操作之间的顺序。
考虑以时间为下标建立线段树，每个操作加入到对应的时间即可。
询问就是询问的时间这一个前缀中最后一个值为 \(k\) 的后缀和。

考虑到同时有 \(1,0,-1\) 的存在，不能直接在线段树上二分。
但是注意到一段后缀移动一个位置和的影响只会是 \(0,1,-1\)，根据这个我们可以得到一个结论：
对于一段区间的后缀最大值 \(mx\)，最小值 \(mi\)，若 \(mi\leq k \leq mx\) ，则目标位置一定在这个区间中。
结论还是比较经典的，根据这个结论直接在线段树上做就行了，然后这道题就结束了，时间复杂度 \(O(qlogn)\)。

code

点击查看代码

#include <bits/stdc++.h>
#define int long long
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc( '\n' )
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
    x = 0 ;rg int fk(0) ; rg char c(gc()) ;
    while(!isdigit(c)) fk |= (c=='-'),c = gc() ;
    while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
    x = (fk?-x:x) ;
    read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
    if(x < 0) pc('-'),x = -x ;
    do stk[++tp] = x%10,x /= 10 ; while(x) ;
    while(tp) pc(stk[tp--]^48) ; print(p...) ;
}
const int N = 1e6+5 ;
int n,q ;
vector<int>e[N] ;
void Solve1()
{
	while(q--)
	{
		int op,le,ri,k ; read(op,le,ri) ;
		if(op == 0) 
		{
			read(k) ;
			FOR(i,le,ri,1) e[i].pb(k) ;
		}
		if(op == 1)
		{
			FOR(i,le,ri,1) if(e[i].size())
				e[i].pop_back() ;
 		}
		if(op == 2) 
		{
			if(e[le].size() < ri) puts("Error") ;
			else print(e[le][e[le].size()-ri]),enter ;
		}
	}
}
struct Node
{
	int l,r,g ;
	vector<int>p ;
}tr[N<<2] ;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define g(x) tr[x].g
#define mid (tr[x].l+tr[x].r>>1)
void Build(int x,int le = 1,int ri = n)
{
	tr[x].l = le,tr[x].r = ri ; if(le == ri) return ;
	Build(ls(x),le,mid),Build(rs(x),mid+1,ri) ;
}
inline void f(int x,int k,vector<int>&p)
{
	while(k && tr[x].p.size()) tr[x].p.pop_back(),--k ;
	g(x) += k ; for(auto v:p) tr[x].p.pb(v) ;
}
inline void down(int x)
{
	f(ls(x),g(x),tr[x].p),f(rs(x),g(x),tr[x].p),g(x) = 0,tr[x].p.clear() ;
}
void Modify(int x,int le,int ri,int k)
{
	if(tr[x].l >= le && tr[x].r <= ri) {tr[x].p.pb(k) ; return ;}
	down(x) ; if(le <= mid) Modify(ls(x),le,ri,k) ; if(mid < ri) Modify(rs(x),le,ri,k) ;
}
void Erase(int x,int le,int ri)
{
	if(tr[x].l >= le && tr[x].r <= ri)
	{
		if(tr[x].p.size()) tr[x].p.pop_back() ;
		else ++g(x) ; return ;
	}
	down(x) ; if(le <= mid) Erase(ls(x),le,mid) ; if(mid < ri) Erase(rs(x),mid+1,ri) ;
}
int Query(int x,int k,int l)
{
	if(tr[x].l == tr[x].r) return tr[x].p.size()>=l?tr[x].p[tr[x].p.size()-l]:-1 ;
	down(x) ; return (k <= mid) ? Query(ls(x),k,l) : Query(rs(x),k,l) ;
}
void Solve2()
{
	Build(1) ;
	while(q--)
	{
		int op,le,ri,w ; read(op,le,ri) ;
		if(op == 0) read(w),Modify(1,le,ri,w) ;
		if(op == 1) Erase(1,le,ri) ;
		if(op == 2)
		{
			int p = Query(1,le,ri) ;
			if(~p) print(p),enter ;
			else puts("Error") ;
		}
	}
}
signed main()
{
    // freopen(".in","r",stdin) ;
    // freopen(".out","w",stdout) ;
    read(n,q) ;
    if(n <= 5000 && q <= 5000) Solve1() ; 
    else Solve2() ;
	return 0 ;
}