摘要:莫队+multiset+链表

SP20644 ZQUERY - Zero Query

题面

题目分析

看到数据范围于是想要用莫队做.

维护一个前缀和,答案就变成了区间内最远的两个相同的数.

因为是前缀和所以把区间转化成了左闭右开的.

对每个数开一个大根堆和一个小根堆来维护.

但是发现不好撤销对答案的影响,于是使用回滚莫队,每次固定一个块,莫队右端点向右延伸展,左端点每次询问延伸后撤回.

不过因为同时维护了大根堆和小根堆,莫队撤回的时候弹出节点就出了问题,当前的值不一定同时是最小值和最大值,就弹出了其他的数.

所以换成了set,删除的时候二分出来,加入贡献的时候用迭代器取首尾,正确性是没问题了,然而t飞…

于是发现答案并非无法撤销,可以维护一个链表链接相同的数,莫队端点更新的时候更新链表就可以了.

然后当前元素的距离使用一个multiset来维护,特判一下只有一个元素的情况.

代码

set

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
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define lowbit(x) (x&-x)
#define endl putchar('\n')
typedef long long lxl;
const lxl maxn=50010;
lxl n,m,len,tot,l=1,r=0,_l,_r,__l,NowAns,tmp,LastBlock;
lxl s[maxn],l_[maxn],r_[maxn],pos[maxn],ans[maxn];
std::set<lxl>set1[maxn<<1],set2[maxn<<1];
std::set<lxl>::iterator it;
struct _Query
{
lxl l,r,id;
inline bool operator <(const _Query &another)const
{
if(pos[l-1]!=pos[another.l-1])return pos[l-1]<pos[another.l-1];
return r<another.r;
}
}q[maxn];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void bulid()
{
len=(n+1)/sqrt((n+1)*2/3),tot=(n+1)/len;
for(R int i(1);i<=tot;++i)l_[i]=(i-1)*len+1,r_[i]=i*len;
if(r_[tot]<n+1)++tot,l_[tot]=r_[tot-1]+1,r_[tot]=n+1;
for(R int i(1);i<=tot;++i)
for(R int j(l_[i]);j<=r_[i];pos[j]=i,++j);
}
inline void del(lxl x)
{
if(!set1[s[x]+maxn].empty())
{
it=set1[s[x]+maxn].lower_bound(x);
if(it==set1[s[x]+maxn].end())return;
set1[s[x]+maxn].erase(it);
}
}
inline void add(lxl x,lxl &FAns)
{
if(!set1[s[x]+maxn].empty())
{
FAns=std::max(FAns,x-*(it=set1[s[x]+maxn].begin()));
it=set1[s[x]+maxn].end(),--it;
FAns=std::max(FAns,*it-x);
}
set1[s[x]+maxn].insert(x);
}
int main(void)
{
n=read(),m=read();
for(R int i(2);i<=n+1;s[i]=read(),s[i]+=s[i-1],++i);
bulid();
for(R int i(1);i<=m;q[i].l=read()+1,q[i].r=read()+1,q[i].id=i,++i);
std::sort(q+1,q+1+m);
for(R int i(1);i<=m;++i)
{
_l=q[i].l-1,_r=q[i].r;
if(pos[_l]==pos[_r])
{
for(R int j(_l);j<=_r;++j)
{
if(!set2[s[j]+maxn].empty())
{
ans[q[i].id]=std::max(ans[q[i].id],j-*(it=set2[s[j]+maxn].begin()));
it=set2[s[j]+maxn].end(),--it;
ans[q[i].id]=std::max(ans[q[i].id],*it-j);
}
set2[s[j]+maxn].insert(j);
}
for(R int j(_l);j<=_r;++j)
if(!set2[s[j]+maxn].empty())
{
it=set2[s[j]+maxn].lower_bound(j);
if(it==set2[s[j]+maxn].end())continue;
set2[s[j]+maxn].erase(it);
}
continue;
}
if(pos[_l]!=LastBlock)
{
for(;r>r_[pos[_l]];del(r--));
for(;r<r_[pos[_l]];del(r++));
for(;l<r_[pos[_l]]+1;del(l++));
for(;l>r_[pos[_l]]+1;del(l--));
LastBlock=pos[_l],NowAns=0;
}
for(;r<_r;add(++r,NowAns));
tmp=NowAns,__l=l;
for(;__l>_l;add(--__l,tmp));
ans[q[i].id]=tmp;
for(;__l<l;del(__l++));
}
for(R int i(1);i<=m;++i)printf("%lld\n",ans[i]);
return 0;
}
/*
10 2
-1 -1 -1 -1 -1 -1 -1 1 -1 -1
2 9
3 4
*/

链表+multiset

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 "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl maxn=50010;
lxl n,m,len,l=1,r;
lxl pos[maxn],l_[maxn],r_[maxn],ans[maxn],s[maxn],min[maxn<<1],max[maxn<<1];
std::multiset<lxl>set;
struct _Query
{
lxl l,r,id;
inline bool operator <(const _Query &another)const
{
if(pos[l]!=pos[another.l])return pos[l]<pos[another.l];
if(pos[l]^1)return r>another.r;
return r<another.r;
}
}q[maxn];
inline void del(lxl x)
{
lxl tmp=s[x]+maxn;
if(min[tmp]==max[tmp]){min[tmp]=INF,max[tmp]=-1;return;}
set.erase(set.lower_bound(max[tmp]-min[tmp]));
if(min[tmp]==x)min[tmp]=r_[x];
else if(max[tmp]==x)max[tmp]=l_[x];
if(min[tmp]!=max[tmp])set.insert(max[tmp]-min[tmp]);
}
inline void add(lxl x)
{
lxl tmp=s[x]+maxn;
if(!(~max[tmp])){max[tmp]=min[tmp]=x;return;}
if(max[tmp]!=min[tmp])set.erase(set.lower_bound(max[tmp]-min[tmp]));
if(min[tmp]>x)
{
l_[min[tmp]]=x;
r_[x]=min[tmp];
min[tmp]=x;
}
else if(max[tmp]<x)
{
r_[max[tmp]]=x;
l_[x]=max[tmp];
max[tmp]=x;
}
set.insert(max[tmp]-min[tmp]);
}
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
int main(void)
{
memset(max,-1,sizeof max),memset(min,0x3f,sizeof min);
n=read(),m=read();
len=n/sqrt(n*2/3);
for(R int i(1);i<=n;s[i]=read()+s[i-1],++i);
for(R int i(1);i<=n;++i)pos[i]=i/len+1;
for(R int i(1);i<=m;q[i].l=read(),q[i].r=read(),q[i].id=i,++i);
std::sort(q+1,q+1+m);
set.insert(0);
for(R int i(1);i<=m;++i)
{
lxl _l=q[i].l-1,_r=q[i].r;
for(;r<_r;add(++r));
for(;l>_l;add(--l));
for(;r>_r;del(r--));
for(;l<_l;del(l++));
ans[q[i].id]=*(--set.end());
}
for(R int i(1);i<=m;printf("%lld\n",ans[i]),++i);
return 0;
}