P7560 [JOISC 2021 Day1] フードコート
神奇的换维扫描线。
直接做感觉十分困难，因为是区间操作，并且清空到 $0$ 之后就不再清空，查询不好处理到底是第几个人。但是如果知道了这个点的操作序列，问题就简单很多。询问是单点查询并且可以离线。综合上面所有因素，考虑换一维扫描线：对序列维扫描，横轴为序列维，纵轴为操作序列即时间维。
一个操作 $1,2$，差分后，看成在 $L$ 处出现，$R+1$ 处消失。现在考虑对于一个序列上的位置，求出了它对应的操作序列之后如何处理。
虽然一个点可能被清空多次，但是我们只关心最后一次清空的位置和之后的操作。有一个性质：如果存在清空，则最后一次清空的位置一定是操作序列的前缀和最小值，原因显然：前一次清空和本次清空之间的和必须为负数才能再次产生清空。
理一下思路：需要维护前缀前缀和最小值，支持动态增删，和找出一个操作位置之后的减的和，找出加的和大于一个值的第一个位置。可以用线段树维护时间维。加、删就直接在对应位置上加减。
对于查询，找出它前面前缀和最小值的位置。如果前缀和最小值非负，则证明没有出现清空操作。找出前面一共走了多少人，然后线段树上二分到对应的加人操作。
如果前缀和最小值小于 $0$，则证明在该位置上清空到了 $0$ 并且是最后一个清空到 $0$ 的位置，在它之后像上面一样计算。
复杂度 $\mathcal O(q\log q)$。
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
int n,m,q,typ[250010],ans[250010],col[250010];
struct Node{int pos,x,opt;};
vector<Node> ve[250010];
namespace Segment
{
struct NNode{int l,r,sum,add,minn,mini;}t[1000010];
inline void update(int p)
{
t[p].minn=min(t[p*2].minn,t[p*2].sum+t[p*2+1].minn);
if(t[p*2].minn==t[p].minn)t[p].mini=t[p*2].mini;
else t[p].mini=t[p*2+1].mini;
t[p].sum=t[p*2].sum+t[p*2+1].sum;
t[p].add=t[p*2].add+t[p*2+1].add;
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r)return t[p].mini=l,void();
int mid=l+((r-l)>>1);
build(p*2,l,mid),build(p*2+1,mid+1,r),update(p);
}
void modify(int p,int x,int y,int typ=0)
{
if(t[p].l==t[p].r)return t[p].sum+=y,typ?t[p].add+=y:0,t[p].minn=min(0ll,t[p].sum),void();
if(x<=t[p*2].r)modify(p*2,x,y,typ);else modify(p*2+1,x,y,typ);
update(p);
}
NNode ask(int p,int x)
{
if(x>=t[p].r)return t[p];
if(x<=t[p*2].r)return ask(p*2,x);
NNode nd=ask(p*2+1,x),ans={0,0,nd.sum+t[p*2].sum,0,min(t[p*2].minn,t[p*2].sum+nd.minn),0};
if(ans.minn==t[p*2].minn)ans.mini=t[p*2].mini;else ans.mini=nd.mini;
return ans;
}
int query(int p,int st,int &x)
{
if(st<=t[p].l)
{
if(t[p].add<x)return x-=t[p].add,0;
if(t[p].l==t[p].r)return t[p].l;
if(t[p*2].add>=x)
return query(p*2,st,x);
x-=t[p*2].add;
return query(p*2+1,st,x);
}
if(st<=t[p*2].r)
{
int t=query(p*2,st,x);
if(t)return t;
}
return query(p*2+1,st,x);
}
void print(int p)
{
if(t[p].l==t[p].r)write(t[p].l),write(t[p].r),write(t[p].sum),write(t[p].add),write(t[p].minn),write(t[p].mini,'\n');
if(t[p].l==t[p].r)return;
print(p*2),print(p*2+1);
}
int asksum(int p,int l,int r)
{
if(l<=t[p].l&&r>=t[p].r)return t[p].sum-t[p].add;
int s=0;
if(l<=t[p*2].r)s+=asksum(p*2,l,r);
if(r>t[p*2].r)s+=asksum(p*2+1,l,r);
return s;
}
}
using namespace Segment;
inline void mian()
{
read(n,m,q);int opt,x,y,z,t;
for(int i=1;i<=q;++i)
{
read(opt);
if(opt==1)read(x,y,z,t),col[i]=z,ve[x].eb((Node){i,t,1}),ve[y+1].eb((Node){i,-t,1});
else if(opt==2)read(x,y,z),ve[x].eb((Node){i,z,2}),ve[y+1].eb((Node){i,-z,2});
else read(x,y),typ[i]=1,ve[x].eb((Node){i,y,3});
}
build(1,1,q);
for(int i=1;i<=n;++i)
{
for(auto nd:ve[i])
{
if(nd.opt==1)modify(1,nd.pos,nd.x,1);
else if(nd.opt==2)modify(1,nd.pos,-nd.x);
else
{
NNode nd2=ask(1,nd.pos);
if(nd2.minn>=0)
{
int cut=-asksum(1,1,nd.pos)+nd.x;
ans[nd.pos]=query(1,1,cut);
}
else
{
int cut=-asksum(1,nd2.mini+1,nd.pos)+nd.x;
ans[nd.pos]=query(1,nd2.mini+1,cut);
}
}
}
}
for(int i=1;i<=q;++i)if(typ[i])write(ans[i]>i?0:col[ans[i]],'\n');
}