Codeforces Round #136 (Div. 1) B. Little Elephant and Array
10244 단어 세그먼트 트리
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 알고리즘 14427번 : 수열과 쿼리 15길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
