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 ;
}
...
这道题难吗，感觉也不难。
考试的时候也想到过转化为 \(1,-1\) 这种操作，但是在得到操作序列个顺序卡住了，然后就寄了。
这道题首先用离线的方式得到了操作序列，然后又以时间为下标建立了线段树的到顺序，消掉一维。
其实还是很套路的，看来还是我太菜了/kk。