hh的项链：不带修改维护区间种类数

https://www.luogu.com.cn/problem/P1972#submit

山东理工大学系列赛

https://acm.sdut.edu.cn/onlinejudge3/contests/4125/problems/D

Description

给定一个长度为 nn 的序列 aa 和 mm 次询问，对于第 ii 次询问给定两个正整数 [l,r][l, r]，判断 al∼ara_l \sim a_r 是否为合法序列。

定义：若区间 [l,r][l, r] 中存在一个数 aia_i (l≤i≤r)(l \le i \le r) 出现在 [1,l−1][1, l - 1] 或 [r+1,n][r + 1, n] 中则为不合法序列。

Input

输入的第一行包含两个正整数 n,mn, m (1≤n,m≤105)(1 \le n, m \le 10 ^ 5)

输入的第二行包含 nn 个数 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n (1≤ai≤105)(1 \le a_i \le 10 ^ 5)

接下来 mm 行每行给定两个正整数 l,rl, r (1≤l≤r≤n)(1 \le l \le r \le n)

Output

对于每个询问，判断是否为合法序列，如果是输出 YES，否则输出 NO

https://acm.sdut.edu.cn/onlinejudge3/contests/4125/problems/D

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>

#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int a[N];
int l[N],r[N];//l数组表示1-i中有多少种数
int f[N];//记录是否出现
int c[N];//树状数组维护前缀和

bool ans[N];//记录答案用的
struct node{
    int l,r;
    int id;//标记这个区间是第几次输入进来的
    //这个是用于告诉sort如何排序
    //按照右边界从小到大排序
    bool operator < (const node &x) const{
            return r<x.r;
    }
}tre[N];
//树状数组的更新操作
void add(int x,int k){
    for(int i=x;i<=n;i+=(i&-i)) c[i]+=k;
}
int sum(int x){//树状数组的求和操作
    int an=0;
    for(int i=x;i;i-=(i&-i)) an+=c[i];
    return an;
}
//我们可以知道这个从1-l到1-r区间增加了多少种数，这个是增量，如果按照题目要求应该
//满足这个区间的数都是新加的，也就是区间俩边都没有，由于还有右边，所以我们
//不能 边计算这个区间有多少种数 边统计增量种数，这会增加一个常数
//没有提前预处理的方法好
//如果一个区间内的种类数==增量的种类数，这说明这个区间的数没有一个属于
//之前的任何一个种类，否则不满足上面的公式
//
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	set<int>s1,s2;
	for(int i=1;i<=n;i++){
		s1.insert(a[i]);
		l[i]=s1.size();
	}
	for(int i=n;i>=1;i--){
		s2.insert(a[i]);
		r[i]=s2.size();
	}
	 for(int i=1;i<=m;i++)
    {
        cin>>tre[i].l>>tre[i].r;tre[i].id=i;
    }
    sort(tre+1,tre+1+m);
	
	int k=1;
	for(int i=1;i<=m;i++)
    {
    	int st=tre[i].l,ed=tre[i].r;
        for(k;k<=tre[i].r;k++)
        {
            if(f[a[k]])//如果这个值出现
            {
                add(f[a[k]],-1);//就从上次出现的位置开始减
            }
            add(k,1);//这个位置再重新加
            f[a[k]]=k;//记录这次出现的位置
        }
        int len=sum(tre[i].r)-sum(tre[i].l-1);//求答案
if(l[ed]-l[st-1]==len&&r[st]-r[ed+1]==len)ans[tre[i].id]=1;
    }
     for(int i=1;i<=m;i++){
     if(ans[i])cout<<"YES"<<endl;
     else cout<<"NO"<<endl;
     }
}
int main() {
    cin.tie(0);
    
    ios::sync_with_stdio(false);

    int t;
   //cin>>t;
     t=1;
    while (t--) {
solve();
    }
    return 0;
}