sicily 1686

//一整天被卡在这道题中。。 //经过5次小改函数，3次大改刷了重写。。 //TLE 4次 WA 七八次 //一开始一位是水题用自己种过的树水。。4次TLE后 //重新看看那篇大牛写的文章。。原来处理一段数据需要用标记。。果断重写 //之后更纠结，因为把本来标记线段节点当线段边界用，果断WA4次 //之后还水，各种数据一直给力，各种WA。。 //好吧。。我算是服了，重写。。 //Accept出来，都很伤心。。。被以为是水题的题卡了前后5 6小时， //学到了。。。对一段操作的时候。。用r存储一段的公共元素，要用的时候+上就可以了 //然后就是拆分的时候这个r要往下传 //1.53s。。 #include <iostream> #include <cstring> #include <cstdio> #define I 100100 using namespace std; int n,k,a,b,c; char m; struct Seq { int x,y; int mx; int z; int r; }seq[4*I]; void build_Tree( int p,int x,int y ) { seq[p].mx = 0; seq[p].x = x; seq[p].y = y; seq[p].r = 0; seq[p].z = x; if ( x == y ) return ; int mid = ( x + y ) / 2; build_Tree( 2*p, x,mid ); build_Tree( 2*p+1,mid+1,y); } int find( int p,int x,int y,int &z ) { if( seq[p].x >= x && seq[p].y <= y ) { z = seq[p].z; return seq[p].mx; } seq[2*p].r += seq[p].r; //删除破坏线段公有元素 seq[2*p].mx += seq[p].r; seq[2*p+1].r += seq[p].r; seq[2*p+1].mx += seq[p].r; seq[p].r = 0; int mid = ( seq[p].x + seq[p].y ) / 2; if( y <= mid ) return find( 2*p,x,y,z ); if( x > mid ) return find( 2*p+1,x,y,z ); int z1,z2; int k1 = find( 2*p,x,y,z1 ),k2 = find( 2*p+1,x,y,z2 ); if( k1 < k2 ) { z = z2; return k2; } z = z1; return k1; } void re_i( int p,int x,int y ) { if( x <= seq[p].x && y >= seq[p].y ) { seq[p].mx += c; seq[p].r += c; return ; } seq[2*p].r += seq[p].r; //往下传r 因为其中一段加上c后破坏了 mx seq[2*p].mx += seq[p].r; seq[2*p+1].r += seq[p].r; seq[2*p+1].mx += seq[p].r; seq[p].r = 0; int mid = ( seq[p].x + seq[p].y ) / 2; if( mid >= x ) re_i(2*p,x,y); if( mid < y ) re_i(2*p+1,x,y); if( seq[2*p].mx < seq[2*p+1].mx ) { seq[p].z = seq[2*p+1].z; seq[p].mx = seq[2*p+1].mx; } else { seq[p].z = seq[2*p].z; seq[p].mx = seq[2*p].mx; } } int main() { //freopen("1.txt","r",stdin ); while( scanf("%d%d",&n,&k) && 0 != n ) { build_Tree(1,1,n); //build_Tree(1,1,100000) 贡献WA while ( k-- ) { cin>>m; if( m == 'I' ) { scanf( "%d%d%d",&a,&b,&c ); re_i( 1,a,b ); } else { scanf( "%d%d",&a,&b ); int r; int zz = find( 1,a,b,r ); c = -zz; cout<<zz<<endl; if( zz != 0 ) re_i( 1,r,r ); } } } return 0; }