3. 风蚀
题目ID：24476必做题文件操作100分
订正得分
赛中得分
最新提交：
Wrong Answer
30 分
历史最高：
Wrong Answer
30 分
时间限制: 2000ms
空间限制: 524288kB
输入文件名: wind.in
输出文件名: wind.out
题目描述
考古队发现了一排古老的岩柱，一共有
n
n 根，从左到右编号为
1
1 到
n
n。
第
i
i 根岩柱有一个坚硬度
a
i
a
i
。保证所有坚硬度 两两不同。
考古队会对一段连续岩柱做“风蚀实验”。
设这一段是从第
l
l 根到第
r
r 根。实验按“天”进行。
第 1 天，这一整段岩柱看成一个完整的连续块。
之后每一天的操作会对当前所有连续块分别进行同样的操作，彼此互不影响：
在这个连续块里，找出坚硬度最小的那一根岩柱；
这根岩柱会在这一天被风蚀掉；
记下一个二元组
(
L
,
R
)
(L,R)，其中：
L
L 表示这根岩柱左边、仍属于这个连续块的岩柱数量；
R
R 表示这根岩柱右边、仍属于这个连续块的岩柱数量。
因为所有坚硬度两两不同，所以每个连续块里“最小的那根岩柱”总是唯一的。
把这一天所有连续块得到的二元组，按照这些连续块从左到右的顺序依次写下来，就得到这一天的 风蚀记录。
当天结束后，被风蚀掉的岩柱消失。剩下的岩柱会分裂成若干个新的连续块，进入下一天。
如果某一天开始时已经没有岩柱了，那么这一天以及之后所有天的风蚀记录都视为空序列。
现在有
q
q 次询问。
每次询问给出两段连续区间
[
l
1
,
r
1
]
[l
1
,r
1
] 和
[
l
2
,
r
2
]
[l
2
,r
2
]。
如果这两段区间在 每一天 得到的风蚀记录都完全相同，就称它们是 同谱 的。
你需要对每次询问回答这两段区间是否同谱。
输入格式
第一行两个整数
n
,
q
n,q。
第二行
n
n 个整数
a
1
,
a
2
,
…
,
a
n
a
1
,a
2
,…,a
n
，表示每根岩柱的坚硬度。保证它们两两不同。
接下来
q
q 行，每行四个整数
l
1
,
r
1
,
l
2
,
r
2
l
1
,r
1
,l
2
,r
2
，表示一次询问。
输出格式
对于每次询问输出一行。
如果两段区间同谱，输出 Yes；否则输出 No。
样例
Input 1
7 5
3 1 4 2 7 5 6
1 3 5 7
1 4 4 7
2 4 5 7
1 1 4 4
3 6 4 7
Output 1
Yes
No
No
Yes
No
样例解释
区间
[
1
,
3
]
[1,3] 的序列是
(
3
,
1
,
4
)
(3,1,4)，区间
[
5
,
7
]
[5,7] 的序列是
(
7
,
5
,
6
)
(7,5,6)。它们第一天都会删掉中间位置的最小值，得到记录
(
1
,
1
)
(1,1)；第二天左右各剩一个单点块，记录也完全一样，所以它们同谱。
区间
[
1
,
4
]
[1,4] 和
[
4
,
7
]
[4,7] 第一天删掉最小值后，左右剩余规模就不同，因此不同谱。
数据范围
对于所有测试数据，均有：
1
≤
n
,
q
≤
5
×
1
0
5
1≤n,q≤5×10
5
；
对于所有
1
≤
i
≤
n
1≤i≤n，均有
1
≤
a
i
≤
n
1≤a
i
≤n，且
a
1
,
a
2
,
…
,
a
n
a
1
,a
2
,…,a
n
两两不同；
对于所有询问，均有
1
≤
l
1
≤
r
1
≤
n
,
1
≤
l
2
≤
r
2
≤
n
1≤l
1
≤r
1
≤n, 1≤l
2
≤r
2
≤n。
测试点编号
n
≤
n≤
q
≤
q≤ 特殊性质
1 500 500 无
2 2000 2000 无
3 3000 3000 无
4，5 50000 50000 A
6 100000 100000 B
7 100000 100000 C
8 100000 100000 D
10 100000 100000 E
9，11 200000 100000 无
12 200000 100000 D
13，14 300000 200000 无
15，16 300000 200000 D
17 - 20 500000 500000 无
特殊性质 A：对于所有询问，均有
r
1
−
l
1
+
1
≤
32
r
1
−l
1
+1≤32 且
r
2
−
l
2
+
1
≤
32
r
2
−l
2
+1≤32。
特殊性质 B：数组严格递增，即对于所有
1
≤
i
≤
n
1≤i≤n，均有
a
i
=
i
a
i
=i。
特殊性质 C：数组严格递减，即对于所有
1
≤
i
≤
n
1≤i≤n，均有
a
i
=
n
−
i
+
1
a
i
=n−i+1。
特殊性质 D：数组为交错排列，即
a
=
(
1
,
n
,
2
,
n
−
1
,
3
,
n
−
2
,
…
)
.
a=(1,n,2,n−1,3,n−2,…).
特殊性质 E：对于所有询问，均有
l
1
=
l
2
=
1
l
1
=l
2
=1。
附件
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5+5;
const int mod = 1e9+7;
int n,q,a[N],pre[N],check[N];
int h[N],top,num;
const int B = 223;
vector<int> vis[N];
int c[N],ans[2*N],power[N];
struct node{
int l,r,id;
}s[2*N];
map<int,int> mp;
inline int lowbit(int o){
return o & -o;
}
void add(int a,int w){
int i = a;
while(i<=n){
// cout<<i<<endl;
c[i] = (c[i]+w)%mod;
i += lowbit(i);
}
return ;
}
int query(int a){
int res = 0;
int i = a;
while(i>0){
res = (res+c[i])%mod;
i -= lowbit(i);
}
return res;
}
void init(){
power[0] = 1;
for(int i = 1; i<=n; i++){
power[i] = (power[i-1]*B)%mod;
}
// cout<<power[1]<<endl;
return ;
}
int quick(int a,int b){
int res = 1;
while(b>0){
if(b & 1) res=(res*a)%mod;
a = (a*a)%mod;
b >>= 1;
}
return res;
}
bool cmp(node a,node b){
return a.l>b.l;
}
signed main(){
freopen("wind.in","r",stdin);
freopen("wind.out","w",stdout);
cin>>n>>q;
init();
for(int i = 1; i<=n; i++){
cin>>a[i];
}
// cout<<1<<endl;
for(int i = 1; i<=n; i++){
while(top>0 && a[h[top]]>=a[i]) top--;
pre[i] = h[top];
top++;
vis[pre[i]].push_back(i);
// cout<<pre[i]<<' ';
h[top] = i;
}
cout<<endl;
for(int i = 1; i<=q; i++){
int l1,l2,r1,r2;
cin>>l1>>r1>>l2>>r2;
s[i*2-1].l=l1,s[i*2-1].r=r1,s[i*2].l=l2,s[i*2].r=r2;
// s[i*2-1].pos = i*2;
s[i*2-1].id=s[i*2].id=i;
check[i] = -1;
}
// cout<<1<<endl;
sort(s+1,s+2*q+1,cmp);
num = 1;
for(int i = n; i>=1; i--){
// cout<<"111 "<<i<<endl;
for(int j = 0; j<vis[i].size(); j++){
// cout<<vis[i][j]<<' ';
add(vis[i][j],(vis[i][j]-i)*power[vis[i][j]]%mod);
// cout<<vis[i][j]<<" "<<(vis[i][j]-i)*power[vis[i][j]]%mod<<endl;
}
// cout<<22<<endl;
while(s[num].l == i){
int l=s[num].l,r=s[num].r;
ans[num] = (query(r)-query(l-1)+mod)%mod*quick(quick(B,l),mod-2)%mod;
// cout<<endl;
// cout<<l<<" "<<r<<endl;
// cout<<query(r)<<' '<<query(l-1)<<endl;
// cout<<ans[num]<<endl;
num++;
}
// cout<<endl;
}
for(int i = 1; i<=2*q; i++){
// cout<<"111 "<<s[i].id<<endl;
if(check[s[i].id] == -1){
check[s[i].id] = ans[i];
}else{
// cout<<s[i].id<<endl;
if(check[s[i].id] == ans[i]) check[s[i].id]=1;
else check[s[i].id]=0;
}
}
for(int i = 1; i<=q; i++){
if(check[i]) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
