去年省赛原题..
今年基本上把线段树忘记的差不多了。今天又敲了一遍。发现自己的输入处理还不错。
这种类型的弱爆了线段树...
由于思想不细致，导致WA了很久，看来以后要细心一点了！
weak node
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 22 Accepted Submission(s) : 7
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Country C preparing to attack Country J, but the shortage of troops Country C, Country C to find out the location of weak Country J defense.
Input
Line 1: n m(1<=n<=100,000, 1<=m<=120,000 )
Line 2: n numbers, respectively said the defense force of the Country J n nodes
Line 3 to 2+m: m action, expressed as follows
find:(i,j)
From i to j nodes to identify the weakest defense of the node, and the output of Defense
move:(i1,i2.....)
These points will move relative to each other position
For example, if [8,7,6,5,4,3,2,1], then move(3,5,7) yields [8,7,4,5,2,3,6,1]
Line 2: n numbers, respectively said the defense force of the Country J n nodes
Line 3 to 2+m: m action, expressed as follows
find:(i,j)
From i to j nodes to identify the weakest defense of the node, and the output of Defense
move:(i1,i2.....)
These points will move relative to each other position
For example, if [8,7,6,5,4,3,2,1], then move(3,5,7) yields [8,7,4,5,2,3,6,1]
Output
For each find, print the weakest defense of the value
Sample Input
8 3 8 7 6 5 4 3 2 1 find(2,5) move(3,5,7) find(2,5)
Sample Output
4 2
#include<iostream>
#define MAXN 111111
#define INF 0x7FFFFFFF
using namespace std;int tree[MAXN<<2];
int min( int a,int b ){ return a<b?a:b; }void PushUp( int rt ){tree[rt]=min( tree[rt<<1],tree[rt<<1|1] );
}void build( int l,int r,int rt )
{if( l==r ){scanf( "%d",&tree[rt] );return ;}int m=(l+r)>>1;build( l,m,rt<<1 );build( m+1,r,rt<<1|1 );PushUp(rt);
}void update( int p,int num,int l,int r,int rt )
{if( l==r ){tree[rt]=num;return ;}int m=(l+r)>>1;if( p<=m )update( p,num,l,m,rt<<1 );elseupdate( p,num,m+1,r,rt<<1|1 );PushUp(rt);
}int query( int L,int R,int l,int r,int rt )
{if( L<=l&&r<=R ){return tree[rt];}int m=(l+r)>>1;int ret=INF;if( L<=m ) ret=min( ret,query(L,R,l,m,rt<<1) );if( m<R ) ret=min( ret,query(L,R,m+1,r,rt<<1|1) );return ret;
}void getData( char *s,int *num,int &n )
{int bit;s+=5;while( strlen(s) ){sscanf( s,"%d%n",&num[n++],&bit );s+=bit+1;}
}int main()
{freopen( "J.in","r",stdin );freopen( "Jans.out","w",stdout );int N,M;while( scanf("%d %d",&N,&M )!=EOF ){build(1,N,1);getchar();char str1[11111],str2[11111];int l,r;for( int i=0;i<M;i++ ){gets(str1);int num;if( sscanf(str1,"find(%d,%d)",&l,&r) )printf( "%d\n",query(l,r,1,N,1) );else{int rot[11],n=0;getData( str1,rot,n );int rec=query( rot[0],rot[0],1,N,1);for( int i=0;i<n-1;i++ )update( rot[i],query(rot[i+1],rot[i+1],1,N,1),1,N,1 );update( rot[n-1],rec,1,N,1 );}}}return 0;
}