UESTC 360 Another LCIS

Another LCIS

Time Limit: 1000ms

Memory Limit: 65536KB

This problem will be judged on UESTC. Original ID: 1425
64-bit integer IO format: %lld Java class name: Main

For a sequence S1,S2,...,SN, and a pair of integers (i, j), if 1 <= i <= j <= N and Si < Si+1 < Si+2 <...< Sj-1 < Sj, then the sequence Si,Si+1,...,Sj is a CIS (Continuous Increasing Subsequence). The longest CIS of a sequence is called the LCIS (Longest Continuous Increasing Subsequence).

In this problem, we will give you a sequence first, and then some “add” operations and some “query” operations. An add operation adds a value to each member in a specified interval. For a query operation, you should output the length of the LCIS of a specified interval.

Input

The first line of the input is an integer T, which stands for the number of test cases you need to solve.

Every test case begins with two integers N, Q, where N is the size of the sequence, and Q is the number of queries. S1,S2,...,SN are specified on the next line, and then Q queries follow. Every query begins with a character ‘a’ or ‘q’. ‘a’ is followed by three integers L, R, V, meaning that add V to members in the interval [L, R] (including L, R), and ‘q’ is followed by two integers L, R, meaning that you should output the length of the LCIS of interval [L, R].

T <= 10;
1 <= N, Q <= 100000;
1 <= L <= R <= N;
-10000 <= S1,S2,...,SN, V <= 10000.

Output

For every test case, you should output "Case #k:" on a single line first, where k indicates the case number and starts at 1. Then for every ‘q’ query, output the answer on a single line. See sample for more details.

Sample Input

1
5 6
0 1 2 3 4
q 1 4
a 1 2 -10
a 1 1 -6
a 5 5 -4
q 2 3
q 4 4

Sample Output

Case #1:
4
2
1

Source

The 9th UESTC Programming Contest Preliminary

解题：线段树往死里搞

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 100010;
  4 struct node {
  5     int ret,lv,rv,lsum,rsum,lazy;
  6 } tree[maxn<<2];
  7 void pushup(int v,int k) {
  8     tree[v].lsum = tree[v<<1].lsum;
  9     tree[v].rsum = tree[v<<1|1].rsum;
 10     tree[v].lv = tree[v<<1].lv;
 11     tree[v].rv = tree[v<<1|1].rv;
 12     if(tree[v].lsum == k - (k>>1) && tree[v<<1].rv < tree[v<<1|1].lv)
 13         tree[v].lsum += tree[v<<1|1].lsum;
 14     if(tree[v].rsum == (k>>1) && tree[v<<1].rv < tree[v<<1|1].lv)
 15         tree[v].rsum += tree[v<<1].rsum;
 16     tree[v].ret = max(tree[v<<1].ret,tree[v<<1|1].ret);
 17     if(tree[v<<1].rv < tree[v<<1|1].lv)
 18         tree[v].ret = max(tree[v].ret,tree[v<<1].rsum + tree[v<<1|1].lsum);
 19 }
 20 void pushdown(int v,int k) {
 21     if(tree[v].lazy) {
 22         tree[v<<1].lazy += tree[v].lazy;
 23         tree[v<<1|1].lazy += tree[v].lazy;
 24         tree[v<<1].lv += tree[v].lazy;
 25         tree[v<<1].rv += tree[v].lazy;
 26         tree[v<<1|1].lv += tree[v].lazy;
 27         tree[v<<1|1].rv += tree[v].lazy;
 28         tree[v].lazy = 0;
 29     }
 30 }
 31 void build(int L,int R,int v) {
 32     tree[v].lazy = 0;
 33     if(L == R) {
 34         tree[v].lsum = tree[v].rsum = 1;
 35         scanf("%d",&tree[v].rv);
 36         tree[v].lv = tree[v].rv;
 37         tree[v].ret = 1;
 38         return;
 39     }
 40     int mid = (L + R)>>1;
 41     build(L,mid,v<<1);
 42     build(mid+1,R,v<<1|1);
 43     pushup(v,R - L + 1);
 44 }
 45 void update(int L,int R,int lt,int rt,int val,int v) {
 46     if(lt <= L && rt >= R) {
 47         tree[v].lazy += val;
 48         tree[v].lv += val;
 49         tree[v].rv += val;
 50         return;
 51     }
 52     pushdown(v,R - L + 1);
 53     int mid = (L + R)>>1;
 54     if(lt <= mid) update(L,mid,lt,rt,val,v<<1);
 55     if(rt > mid) update(mid+1,R,lt,rt,val,v<<1|1);
 56     pushup(v,R - L + 1);
 57 }
 58 int query(int L,int R,int lt,int rt,int v) {
 59     if(lt <= L && rt >= R) return tree[v].ret;
 60     pushdown(v,R - L + 1);
 61     int ret  = 0,mid = (L + R)>>1;
 62     if(lt <= mid) ret = max(ret,query(L,mid,lt,rt,v<<1));
 63     if(rt > mid) ret = max(ret,query(mid+1,R,lt,rt,v<<1|1));
 64     if(lt <= mid && rt > mid && tree[v<<1].rv < tree[v<<1|1].lv)
 65         ret = max(ret,min(mid - lt + 1,tree[v<<1].rsum) + min(rt - mid,tree[v<<1|1].lsum));
 66     pushup(v,R - L + 1);
 67     return ret;
 68 }
 69 int main() {
 70     int T,n,m,x,y,val,cs = 1;
 71     char op[3];
 72     scanf("%d",&T);
 73     while(T--) {
 74         scanf("%d %d",&n,&m);
 75         printf("Case #%d:
",cs++);
 76         build(1,n,1);
 77         while(m--) {
 78             scanf("%s%d%d",op,&x,&y);
 79             if(op[0] == 'a') {
 80                 scanf("%d",&val);
 81                 update(1,n,x,y,val,1);
 82             } else if(op[0] == 'q')
 83                 printf("%d
",query(1,n,x,y,1));
 84         }
 85     }
 86     return 0;
 87 }
 88 /*
 89 1
 90 5 6
 91 0 1 2 3 4
 92 q 1 4
 93 a 1 2 -10
 94 a 1 1 -6
 95 a 5 5 -4
 96 q 2 3
 97 q 4 4
 98 
 99 Case #1:
100 4
101 2
102 1
103 */

View Code