Wuyanru's blog
0%

[PKUWC2024] 栈

发表于 分类于 ，

神秘题目，场下写了两三个小时才写完。

题目链接。

题意

有编号为 的 个栈与 次操作，操作分为三种：

  1. 给区间 的栈各压入 个 ；
  2. 令区间 的栈各弹栈 次。
  3. 查询第 个栈从栈底数第 个元素的和，不存在这个元素即为 。

。

。

。

题解

这题在线显然很不好做。

即使不存在 操作，线段树直接在线维护的话，下放 tag 都需要可持久化平衡树，非常麻烦。

所以考虑离线做法。

先考虑 的时候怎么做，考虑使用类似括号序列的东西维护当前的栈。

如果时刻 是一个入栈操作，那么就相当于往整个序列后面放入 个第 种左括号。

如果时刻 是一个出栈操作，那么相当于往整个序列后面放入 个右括号。

其中，左括号和右括号会在这个序列里互相匹配，最终序列里没有匹配的左括号，就是仍然留在栈内的元素。

如果时刻 是一个查询操作，就是按照上面的规律，查询第 个未被匹配的左括号的和。

在合并两个序列的时候，由于右区间剩余的右括号有可能匹配上左区间剩余的左括号，所以区间合并是不能直接进行的。

但是，只需要楼房重建的技巧，即 push_up 时单边递归的线段树，即可在 的复杂度内解决 的问题。

考虑 更大时， 与它的区别。

考虑从位置 开始，从左向右做扫描线。

扫描到位置 时，我们需要动态维护作用在 上的操作序列。

当从 扫到 时，其实就是删除或增加了一些左右括号。

更新到位置 时，对于一个时刻 的询问，实际就是在问一段前缀 的未匹配左括号区间和，还是可以 得出答案。

具体实现

实现十分麻烦，再讲一下具体细节。

对于一次新增/删除括号的操作，先递归到线段树的叶节点，完成叶节点的修改，难点在于 push_up。

考虑递归 push_up，定义函数 push_up(p,l,r,e) 表示对于一个节点 ，它管理的区间 ，在右边有 个未匹配的右括号时，未匹配的左括号个数以及种类编号和。

不难发现，如果我们在线段树上同时维护两个变量，为考虑右儿子剩余的右括号情况下，左区间的未匹配左括号个数以及种类编号和，上述 push_up 函数每一次就只会在左右儿子中的一个进行递归，单次 push_up 复杂度变为 ，故一次修改的复杂度为 。

再考虑一次查询操作，需要查询线段树上 构成的括号序列里，第 个未匹配左括号的编号种类和。

考虑将其拆为两个前缀 与 的差。

定义函数 get(p,l,r,tim,cnt,e) 表示一个线段树上节点 管理的区间是 ，现在它的右边有额外 个右括号，需要对其 的部分查询前 个未匹配左括号的和

可以发现，若 ，则整个区间都被包含，此时可以进行单边递归计算。

对于剩余 的区间，可以发现这样的区间最多有 个，与普通线段树的复杂度相同，暴力递归即可。

故一次查询的复杂度也是 。

这样，我们就可以在 的复杂度内完成计算。

具体实现看代码。

代码

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
using pal=pair<ll,ll>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
namespace S
{
    ll rest[400001];
    ll sum[400001];
    ll lrest[400001];
    ll lsum[400001];
    ll e[400001];
    pal push_up(int p,int pl,int pr,ll re)
    {
        if(rest[p]<=re) return pal(0,0);
        if(pl==pr)
        {
            int val=sum[p]/rest[p];
            return pal(rest[p]-re,(rest[p]-re)*val);
        }
        int mid=(pl+pr)>>1;
        if(re<=rest[p*2|1])
        {
            auto val=push_up(p*2|1,mid+1,pr,re);
            return pal(val.first+lrest[p],val.second+lsum[p]);
        }
        return push_up(p*2,pl,mid,re-rest[p*2|1]+e[p*2|1]);
    }
    void add(int p,int pl,int pr,int x,int c,int v)
    {
        if(pl==pr)
        {
            if(v==-1) e[p]+=c;
            else
            {
                rest[p]+=c;
                sum[p]+=(ll)c*v;
            }
            return ;
        }
        int mid=(pl+pr)>>1;
        if(x<=mid) add(p*2,pl,mid,x,c,v);
        else add(p*2|1,mid+1,pr,x,c,v);
        auto val=push_up(p*2,pl,mid,e[p*2|1]);
        lrest[p]=val.first,lsum[p]=val.second;
        rest[p]=lrest[p]+rest[p*2|1];
        sum[p]=lsum[p]+sum[p*2|1];
        e[p]=e[p*2]+e[p*2|1]-(rest[p*2]-lrest[p]);
    }
    pal getp(int p,int pl,int pr,int l,int r,ll re)
    {
        if(l<=pl&&pr<=r) return pal(max(rest[p]-re,0ll),max(re-rest[p],0ll)+e[p]);
        int mid=(pl+pr)>>1;pal ans=pal(0,re);
        if(mid<r)
        {
            auto val=getp(p*2|1,mid+1,pr,l,r,ans.second);
            ans.first+=val.first,ans.second=val.second;
        }
        if(l<=mid)
        {
            auto val=getp(p*2,pl,mid,l,r,ans.second);
            ans.first+=val.first,ans.second=val.second;
        }
        return ans;
    }
    ll get(int p,int pl,int pr,int lim,ll r,ll re)
    {
        if(!r) return 0;
        if(pl==pr)
        {
            r=min(r,max(rest[p]-re,0ll));
            ll num=sum[p]/rest[p];
            return r*num;
        }
        if(lim>=pr)
        {
            ll ans=0;int mid=(pl+pr)>>1;
            if(re>=rest[p*2|1]) return get(p*2,pl,mid,lim,r,re-rest[p*2|1]+e[p*2|1]);
            if(lrest[p]>=r) ans=get(p*2,pl,mid,lim,r,e[p*2|1]);
            if(r>lrest[p]) ans=lsum[p]+get(p*2|1,mid+1,pr,lim,r-lrest[p],re);
            return ans;
        }
        pal v1,v2=pal(0,re);ll ans=0;
        int mid=(pl+pr)>>1;
        if(mid<lim) v2=getp(p*2|1,mid+1,pr,1,lim,re);
        v1=getp(p*2,pl,mid,1,lim,v2.second);

        ans=get(p*2,pl,mid,lim,min(r,v1.first),v2.second);
        if(r>v1.first) ans+=get(p*2|1,mid+1,pr,lim,r-v1.first,re);
        return ans;
    }
}
struct node
{
    int tim;
    ll x,y;
};
vc<node>ned[100002];
vc<node>nod[100002];
ll qans[100002];
int n,m;
inline void run(int w)
{
    // if(w%100==0) printf("run %d\n",w);
    for(auto i:nod[w]) S::add(1,1,m,i.tim,i.x,i.y);
    for(auto i:ned[w])
    {
        auto num=S::getp(1,1,m,1,i.tim,0);
        if(i.x>num.first)
        {
            qans[i.tim]=0;
            continue;
        }
        i.y=min(i.y,num.first);
        qans[i.tim]=S::get(1,1,m,i.tim,i.y,0)-S::get(1,1,m,i.tim,i.x-1,0);
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int op=read();qans[i]=-1;
        if(op==1)
        {
            int l=read(),r=read(),x=read(),y=read();
            nod[l].push_back(node{i,x,y});
            nod[r+1].push_back(node{i,-x,y});
        }
        else if(op==2)
        {
            int l=read(),r=read(),x=read(),y=-1;
            nod[l].push_back(node{i,x,y});
            nod[r+1].push_back(node{i,-x,y});
        }
        else
        {
            int x=read();ll l=lread(),r=lread();
            ned[x].push_back(node{i,l,r});
        }
    }
    for(int i=1;i<=n;i++) run(i);
    for(int i=1;i<=m;i++) if(qans[i]!=-1) printf("%lld\n",qans[i]);
    return 0;
}

感谢观看！