GitCode-AI社区

http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1159

因为只有加点  没有删点  所以线段树维护

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

struct date {
    int lt,rt,val,pre;
}node[412345];
bool vis[112345];
void build_tree( int lt,int rt,int t )
{
    node[t].lt = lt;  node[t].rt = rt;
    node[t].val = 0;  node[t].pre = 0;
    if( lt == rt )return;
    int mid = ( lt + rt )>>1;
    build_tree( lt,mid,t<<1 );
    build_tree( mid+1,rt,t<<1|1 );
}
void update( int pre,int pos,int val,int t )
{
    if( node[t].lt == node[t].rt )
    {
        node[t].val += val;
        node[t].pre = pos;
        return;
    }
    if( node[t<<1].rt >= pos )
         update( pre,pos,val,t<<1 );
    else update( pre,pos,val,t<<1|1 );
    if( node[t<<1].val > node[t<<1|1].val )
    {
        node[t].val = node[t<<1].val;
        node[t].pre = node[t<<1].pre;
    }
    else
    {
        node[t].val = node[t<<1|1].val;
        if( node[t<<1].val == node[t<<1|1].val )
             node[t].pre = max( node[t<<1].pre,node[t<<1|1].pre );
        else node[t].pre = node[t<<1|1].pre;
    }
}
int query( int t )
{
    if( node[t].lt == node[t].rt )return node[t].lt;
    if( node[t<<1].val > node[t<<1|1].val )
          return query( t<<1 );
    else  if( node[t<<1].val < node[t<<1|1].val )
          return query( t<<1|1 );
          else if( node[t<<1].pre > node[t<<1|1].pre )
                    return query( t<<1 );
               else return query( t<<1|1 );
}
int main( )
{
    int N,val,x,y; char str[3];
    while( scanf("%d",&N) != EOF && N )
    {
        build_tree( 1,N,1 ); bool fell = false;
        memset( vis,0,sizeof(vis) );
        int k = 1;
        for( int i = 1; i <= N; i++ )
        {
            scanf("%s",&str);
            if( str[0] == 'N' )
            {
                scanf("%d",&val);
                update( i,k++,val,1 );
            }
            if( str[0] == 'I' )
            {
                scanf("%d%d",&x,&y);
                if( vis[x] )continue;
                update( i,x,y,1 );
            }
            if( str[0] == 'D' )
            {
                scanf("%d%d",&x,&y );
                if( vis[x] )continue;
                update( i,x,y*(-1),1 );
            }
            if( str[0] == 'E' )
            {
                scanf("%d",&x);
                update( i,x,(1<<30)*-1,1 );
                vis[x] = true;
            }
            if( str[0] == 'S' )
            {
                if( fell ){printf(" ");}
                fell = true;
                printf("%d",query( 1 ));
            }
        }
        cout<<endl;
    }
    return 0;
}