Codeforces Round #136 (Div. 1) B. Little Elephant and Array

10244 단어 세그먼트 트리
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The Little Elephant loves playing with arrays. He has array a, consisting of n positive integers, indexed from 1 to n. Let's denote the number with index i as ai.
Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers lj and rj (1 ≤ lj ≤ rj ≤ n). For each query lj, rj the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbersalj, alj + 1, ..., arj.
Help the Little Elephant to count the answers to all queries.
Input
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a1, a2, ..., an (1 ≤ ai ≤ 109). Next m lines contain descriptions of queries, one per line. The j-th of these lines contains the description of the j-th query as two space-separated integers lj and rj (1 ≤ lj ≤ rj ≤ n).
Output
In m lines print m integers — the answers to the queries. The j-th line should contain the answer to the j-th query.
Sample test(s)
input
7 2
3 1 2 2 3 3 7
1 7
3 4

output
3

1

, , , 。 , , value, cnt[value] pos[value], (10^5)*(10^5), vector<int>pos[maxn] , (10^5)*(10^5)。

n , cnt[] pos[], cnt[value]==value, , 1~pos[value][0] , 1, pre, ; cnt[value]>value , cnt[value]==value, 1, pos[value][pre[value].id-1]+1~pos[value][pre[value].id] 1, 。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
#define maxn 100060
vector<int>pos[maxn];
int c[maxn],a[maxn],zd[maxn],cnt[maxn],res[maxn];
struct edge{
	int l,r,id;
}pre[maxn];

struct edge1{
	int st,ed,id;
}q[maxn];

struct node{
	int l,r,num,cnt;
}b[4*maxn];

bool cmp(edge1 a,edge1 b){
	return a.ed<b.ed;
}

bool cmp1(edge1 a,edge1 b){
	return a.id<b.id;
}

void build(int l,int r,int i)
{
	int mid;
	b[i].l=l;b[i].r=r;b[i].cnt=0;
	if(l==r){
		b[i].num=0;return;
	}
	mid=(l+r)/2;
	build(l,mid,i*2);
	build(mid+1,r,i*2+1);
}

void update(int l,int r,int num,int i)
{
	int mid;
	if(b[i].l==l && b[i].r==r){
		b[i].cnt+=num;return;
	}
	if(b[i].cnt){
		b[i*2].cnt+=b[i].cnt;
		b[i*2+1].cnt+=b[i].cnt;
		b[i].cnt=0;
	}
	mid=(b[i].l+b[i].r)/2;
	if(r<=mid)update(l,r,num,i*2);
	else if(l>mid)update(l,r,num,i*2+1);
	else{
		update(l,mid,num,i*2);
		update(mid+1,r,num,i*2+1);
	}
}

int question(int id,int i)
{
	int mid;
	if(b[i].l==id && b[i].r==id){
		b[i].num+=b[i].cnt;
		b[i].cnt=0;
		return b[i].num;
	}
	if(b[i].cnt){
		b[i*2].cnt+=b[i].cnt;
		b[i*2+1].cnt+=b[i].cnt;
		b[i].cnt=0;
	}
	mid=(b[i].l+b[i].r)/2;
	if(id<=mid)return question(id,i*2);
	else return question(id,i*2+1);
}

int main()
{
	int n,m,i,j,t,l,r,ind,value;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		for(i=1;i<=m;i++){
			scanf("%d%d",&q[i].st,&q[i].ed);
			q[i].id=i;
		}
		sort(q+1,q+1+m,cmp);
		memset(cnt,0,sizeof(cnt));
		for(i=1;i<=n;i++){
			pos[i].clear();
		}
		
		build(1,n,1);
		ind=1;
		for(i=1;i<=n;i++){
			value=a[i];
			if(value<=n){
				cnt[value]++;
				pos[value].push_back(i);
				if(cnt[value]==value){
					pre[value].l=1;pre[value].r=pos[value][0];pre[value].id=0;
					update(pre[value].l,pre[value].r,1,1);
				}
				else if(cnt[value]>value){
					update(pre[value].l,pre[value].r,-1,1);
					pre[value].id++;
					pre[value].l=pos[value][pre[value].id-1]+1;
					pre[value].r=pos[value][pre[value].id];
					update(pre[value].l,pre[value].r,1,1);
				}
				while(q[ind].ed==i && ind<=m){
					res[q[ind].id]=question(q[ind].st,1);
					ind++;
				}
			}
		}
		sort(q+1,q+1+m,cmp1);
		for(i=1;i<=m;i++){
			if(i==m)printf("%d
",res[i]); else printf("%d ",res[i]); } } return 0; }
코드 2:
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
#define inf 0x7fffffff
#define maxn 100060
#define pi acos(-1.0)
int num[maxn],pre[maxn],a[maxn];
int cnt;
struct node{
    int x,y,idx;
}ques[maxn];

int ans[maxn];
struct node1{
    int l,r,num;
}b[4*maxn];


vector<int>pos[maxn];
vector<int>::iterator p;

bool cmp(node a,node b){
    return a.y<b.y;
}

void build(int l,int r,int i)
{
    int mid;
    b[i].l=l;b[i].r=r;b[i].num=0;
    if(l==r)return;
    mid=(l+r)/2;
    build(l,mid,i*2);
    build(mid+1,r,i*2+1);
}



void update(int l,int r,int num,int i)
{
    int mid;
    if(b[i].l==l && b[i].r==r){
        b[i].num+=num;
        return;
    }
    mid=(b[i].l+b[i].r)/2;
    if(r<=mid)update(l,r,num,i*2);
    else if(l>mid)update(l,r,num,i*2+1);
    else{
        update(l,mid,num,i*2);
        update(mid+1,r,num,i*2+1);
    }
}

void question(int idx,int i)
{
    int mid;
    if(b[i].l==idx && b[i].r==idx){
        cnt+=b[i].num;
        return;
    }
    cnt+=b[i].num;
    mid=(b[i].l+b[i].r)/2;
    if(idx<=mid)question(idx,i*2);
    else question(idx,i*2+1);
}




int main()
{
    int n,m,i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(i=1;i<=m;i++){
            scanf("%d%d",&ques[i].x,&ques[i].y);
            ques[i].idx=i;
        }
        build(1,100000,1);
        sort(ques+1,ques+1+m,cmp);
        memset(ans,0,sizeof(ans));
        memset(num,0,sizeof(num));
        for(i=1;i<=100000;i++){
            pre[i]=1;
            pos[i].clear();
        }

        int wei=1;
        int pre1=1,pre2;
        int flag=1;
        for(i=1;i<=n;i++){
            //printf("---->%d
",i); if(a[i]<=100000){ if(a[i]==1){ if(flag){ flag=0; update(1,i,1,1); pre2=i; } else{ update(pre1,pre2,-1,1); pre1=pre2+1; pre2=i; update(pre1,pre2,1,1); } } else{ num[a[i] ]++; if(num[a[i] ]==a[i] ){ p=pos[a[i] ].begin(); update(pre[a[i] ],*p,1,1); pos[a[i] ].push_back(i); } else if(num[a[i] ]==a[i]+1){ p=pos[a[i] ].begin(); update(pre[a[i] ],*p,-1,1); pre[a[i] ]=*p+1; update(pre[a[i] ],i,1,1); pos[a[i] ].erase(p); pos[a[i] ].push_back(i); num[a[i] ]--; } else{ pos[a[i] ].push_back(i); } } } while(ques[wei].y==i && wei<=m){ int l=ques[wei].x; cnt=0; question(l,1); ans[ques[wei].idx ]=cnt; wei++; } } cnt=0; question(1,1); for(i=1;i<=m;i++){ printf("%d
",ans[i]); } } return 0; }

좋은 웹페이지 즐겨찾기