Editor

Time Limit: 3000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 118 Accepted Submission(s): 38

Problem Description

Sample Input

8 I 2 I -1 I 1 Q 3 L D R Q 2

Sample Output

2 3

Hint

The following diagram shows the status of sequence after each instruction:

Source

Recommend

zhuyuanchen520

这题只要用双向链表模拟一下。

查询最大前缀和，相当于维护一个单调队列。

1 /* ***********************************************  2 Author        :kuangbin  3 Created Time  :2013/8/22 13:38:35  4 File Name     :F:\2013ACM练习\2013多校10\1004.cpp  5 ************************************************ */  6   7 #include 
     
        8 #include 
      
         9 #include 
       
         10 #include 
        
          11 #include 
         
           12 #include 
          
            13 #include 
           
             14 #include 
             15 #include 
             
               16 #include 
              
                17 #include 
               
                 18 #include 
                
                  19 using namespace std; 20 const int MAXN = 1000010; 21 22 int a[MAXN]; 23 int next[MAXN],pre[MAXN],tot; 24 int NewNode() 25 { 26 next[tot] = -1; 27 pre[tot] = -1; 28 tot++; 29 return tot-1; 30 } 31 int root; 32 int sum[MAXN]; 33 vector
                 
                  vec; 34 int now; 35 int n; 36 void init() 37 { 38 tot = 0; 39 root = NewNode(); 40 vec.clear(); 41 n = now = 0; 42 } 43 44 void I(int x) 45 { 46 n++; 47 int t = NewNode(); 48 a[t] = x; 49 pre[t] = now; 50 next[t] = next[now]; 51 if(next[now] != -1)pre[next[now]] = t; 52 next[now] = t; 53 now = t; 54 if(n == 1) 55 { 56 sum[n] = x; 57 vec.push_back(n); 58 } 59 else 60 { 61 sum[n] = sum[n-1] + x; 62 int sz = vec.size(); 63 if(sum[n] > sum[vec[sz-1]]) 64 vec.push_back(n); 65 } 66 } 67 void D() 68 { 69 if(n == 0)return; 70 int sz = vec.size(); 71 if(vec[sz-1] == n) 72 vec.pop_back(); 73 n--; 74 int t = pre[now]; 75 next[t] = next[now]; 76 if(next[now] != -1)pre[next[now]] = t; 77 now = t; 78 } 79 void L() 80 { 81 if(n == 0)return; 82 int sz = vec.size(); 83 if(vec[sz-1] == n) 84 vec.pop_back(); 85 now = pre[now]; 86 n--; 87 } 88 void R() 89 { 90 if(next[now] == -1)return; 91 n++; 92 now = next[now]; 93 if(n == 1) 94 { 95 sum[n] = a[now]; 96 vec.push_back(n); 97 } 98 else 99 {100 int sz = vec.size();101 sum[n] = sum[n-1] + a[now];102 if(sum[n] > sum[vec[sz-1]])103 vec.push_back(n);104 }105 }106 107 108 int Q(int k)109 {110 int sz = vec.size();111 if(vec[sz-1] <= k)112 return sum[vec[sz-1]];113 int t = upper_bound(vec.begin(),vec.end(),k) - vec.begin();114 return sum[vec[t-1]];115 }116 117 118 int main()119 {120 //freopen("in.txt","r",stdin);121 //freopen("out.txt","w",stdout);122 int M;123 int x;124 char op[10];125 while(scanf("%d",&M) == 1)126 {127 init();128 while(M--)129 {130 scanf("%s",&op);131 if(op[0] == 'I')132 {133 scanf("%d",&x);134 I(x);135 }136 else if(op[0] == 'D')137 D();138 else if(op[0] == 'L')139 L();140 else if(op[0] == 'R')141 R();142 else143 {144 scanf("%d",&x);145 printf("%d\n",Q(x));146 }147 }148 }149 return 0;150 }