2022-7-9 personal qualifying 6 competition experience

  The water problem is done quickly ..

 A: Complex greed , All solutions are dp

C: Water problem

E: simulation

H: greedy , Scan line

I: greedy

K,L: Water problem

M: Thinking questions

N: Knapsack mixed template question

J:Poklon

Given an inclusion  N  An array of natural Numbers .

Then you need to answer  Q  Time to ask , Output interval every time  [L,R]  The number of natural numbers that occur exactly twice in .

Input

first line , Two integers  N,Q, Represents the number of array elements and the number of queries .

The second line ,N  It's an integer , Represents an element in an array .

Next  Q  That's ok , Two integers per line  L,R, The interval of inquiry .

New knowledge ： discretization （ No, old knowledge is also new bushi）, offline , Mo team .

Discrete templates

	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	} 
	sort(b+1,b+1+n);
	int len=unique(b+1,b+n+1)-(b+1);
	rep(i,1,n){
		a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	}

Mo team template

struct shu{
	int l,r,id;
}q[500010];
int n,m,block,ans;
int a[N],sum[N],fans[N];
bool cmp(shu a,shu b){
	if ((a.r/block)==(b.r/block)){
		return a.l<b.l;
	} 
	return a.r<b.r;
}
void add(int x)
void del(int x)
void work(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	//block=n/(sqrt(m*2/3));
	block=sqrt(n);
	sort(q+1,q+m+1,cmp);
	int l=0,r=0;
	for(int i=1;i<=m;i++){
		int ql=q[i].l,qr=q[i].r;
		while(l<ql) del(l++);
		while(r>qr) del(r--);
		while(l>ql) add(--l);
		while(r<qr) add(++r);
		fans[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++) cout<<fans[i]<<endl;
}

  Answer key （ The time complexity of being stuck ）

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
#define pii pair<int,int>
using namespace std;
const int N=5e5+5;
struct shu{
	int l,r,id;
}q[500010];
int n,m,block,ans;
int a[N],sum[N],fans[N];
bool cmp(shu a,shu b){
	if ((a.r/block)==(b.r/block)){
		return a.l<b.l;
	} 
	return a.r<b.r;
}
void add(int x){
	if (sum[a[x]]==1) ans++;
	if (sum[a[x]]==2) ans--;
	sum[a[x]]++;
}
void del(int x){
	if (sum[a[x]]==3) ans++;
	if (sum[a[x]]==2) ans--;
	sum[a[x]]--;
}
int b[N];
void work(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	} 
	sort(b+1,b+1+n);
	int len=unique(b+1,b+n+1)-(b+1);
	rep(i,1,n){
		a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	}
	for(int i=1;i<=m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	//block=n/(sqrt(m*2/3));
	block=sqrt(n);
	sort(q+1,q+m+1,cmp);
	int l=0,r=0;
	for(int i=1;i<=m;i++){
		int ql=q[i].l,qr=q[i].r;
		while(l<ql) del(l++);
		while(r>qr) del(r--);
		while(l>ql) add(--l);
		while(r<qr) add(++r);
		fans[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++) cout<<fans[i]<<endl;
}
signed main(){
	CIO;
	work();
	return 0;
}