检查站(线段树)

spoiler posted @ 2011年4月12日 14:49 in 农大月赛解题报告 , 736 阅读
#include<iostream>
#include<stdio.h>
using namespace std;

struct node{
	int r,l,Max;
}s[1000400];

void Build(int x,int y,int num){
	s[num].l=x;
	s[num].r=y;
	s[num].Max=0;
	if(x==y)
		return;
	int mid=(x+y)>>1;
	Build(x,mid,num+num);
	Build(mid+1,y,num+num+1);
}
int modify(int pos,int count,int num){
	if(s[num].l==s[num].r&&s[num].l==pos){
		s[num].Max=count;
	}
	else{
		int mid=(s[num].l+s[num].r)/2;
		if(pos<=mid)
			modify(pos,count,num+num);
		else 
			modify(pos,count,num+num+1);
		s[num].Max=max(s[num+num].Max,s[num+num+1].Max);
	}
}

int main(){
	int cas,i,x;
	int times=1;
	char ch[10];
	scanf("%d",&cas);
	int sn=1;
	int tn=1;
	Build(1,100000,1);
	while(cas--){
		scanf("%s",ch);
		if(ch[0]=='I'){
			scanf("%d",&x);
			modify(tn,x,1);
			tn++;
		}
		else if(ch[0]=='Q'){
			int ans=s[1].Max;
			printf("%d\n",ans);
		}
		else{
			modify(sn,0,1);
			sn++;
		}
	}
	return 0;
#include<iostream>
#include<stdio.h>
using namespace std;

struct node{
	int r,l,Max;
}s[1000400];

void Build(int x,int y,int num){
	s[num].l=x;
	s[num].r=y;
	s[num].Max=0;
	if(x==y)
		return;
	int mid=(x+y)>>1;
	Build(x,mid,num+num);
	Build(mid+1,y,num+num+1);
}
int modify(int pos,int count,int num){
	if(s[num].l==s[num].r&&s[num].l==pos){
		s[num].Max=count;
	}
	else{
		int mid=(s[num].l+s[num].r)/2;
		if(pos<=mid)
			modify(pos,count,num+num);
		else 
			modify(pos,count,num+num+1);
		s[num].Max=max(s[num+num].Max,s[num+num+1].Max);
	}
}

int main(){
	int cas,i,x;
	int times=1;
	char ch[10];
	scanf("%d",&cas);
	int sn=1;
	int tn=1;
	Build(1,100000,1);
	while(cas--){
		scanf("%s",ch);
		if(ch[0]=='I'){
			scanf("%d",&x);
			modify(tn,x,1);
			tn++;
		}
		else if(ch[0]=='Q'){
			int ans=s[1].Max;
			printf("%d\n",ans);
		}
		else{
			modify(sn,0,1);
			sn++;
		}
	}
	return 0;
}}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter