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

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

山东理工大学系列赛

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

Description

给定一个长度为 \(n\) 的序列 \(a\) 和 \(m\) 次询问，对于第 \(i\) 次询问给定两个正整数 \([l, r]\)，判断 \(a_l \sim a_r\) 是否为合法序列。

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

Input

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

输入的第二行包含 \(n\) 个数 \(a_1, a_2, \cdots, a_n\) \((1 \le a_i \le 10 ^ 5)\)

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

Output

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

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

#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;
}