uestc 1425 Another LCIS(線分ツリー最長増分シーケンス)

Another LCIS

Time Limit: 1000 ms Memory Limit: 65536 kB Solved: 100 Tried: 1593

Description

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,...,SNare 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 <= S
1,S
2,...,S
N, 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.

Simple 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

Simple Output

Case #1: 4 2 1

Source

The 9th UESTC Programming Contest Preliminary
タイトル:http://acm.uestc.edu.cn/problem.php?pid=1425
标题:数列をあげて、毎回1つの区間の数を選択したり、これらの数に値を加えたり、これらの数の最長増加シーケンスを聞いたりします.の
分析:この問題は区間を操作して、線分の木を思い浮かべやすいですが、線分の木はそれらの情報を保存してこそ答えを求めることができます.
1.もちろん、区間の最大値を必ず保存し、アップデートするたびに、理首は当然左右のサブツリーの最大値を取ります.のしかし、もし2つの区間がより長いシーケンスを合併したら?
2.各区間の左右境界の値を保存します.これは、2つの区間が統合できるかどうかを判断するのに便利です.これにより、アップデート時により、より優れた値が現れるかどうかを知ることができます.の
3.合并する可能性があることを知っていて、それではどのように现れる更に优れた値を求めて、もちろん、それは中间に现れて、私达は左のセグメントの右端から着くことができる最左端lmostを知っていて、右のセグメントの左端が着くことができる最右端rmost、新しい値はrmost-lmost+1で、だから私达はすべてのセグメントの左端が着くことができる最右端を保存して、右端が着くことができる最左端..つまりlmost,rmost
具体的な実装はコードを見てみましょう
コード:

#include<cstdio>
#include<iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int mm=111111;
int dly[mm<<2],maxlen[mm<<2],vall[mm<<2],valr[mm<<2],rmost[mm<<2],lmost[mm<<2];
void add(int rt,int val)
{
    vall[rt]+=val,valr[rt]+=val;
}
void pushdown(int rt)
{
    add(rt<<1,dly[rt]),add(rt<<1|1,dly[rt]);
    dly[rt<<1]+=dly[rt],dly[rt<<1|1]+=dly[rt];
    dly[rt]=0;
}
void pushup(int rt,int m)
{
    maxlen[rt]=max(maxlen[rt<<1],maxlen[rt<<1|1]);
    vall[rt]=vall[rt<<1],valr[rt]=valr[rt<<1|1];
    rmost[rt]=rmost[rt<<1],lmost[rt]=lmost[rt<<1|1];
    if(valr[rt<<1]<vall[rt<<1|1])
    {
        maxlen[rt]=max(maxlen[rt],rmost[rt<<1|1]-lmost[rt<<1]+1);
        if(rmost[rt]>=m)rmost[rt]=rmost[rt<<1|1];
        if(lmost[rt]<=m+1)lmost[rt]=lmost[rt<<1];
    }
}
void build(int l,int r,int rt)
{
    dly[rt]=0;
    if(l==r)
    {
        scanf("%d",&vall[rt]);
        valr[rt]=vall[rt];
        rmost[rt]=r,lmost[rt]=l,maxlen[rt]=1;
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt,m);
}
void updata(int L,int R,int val,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        add(rt,val);
        dly[rt]+=val;
        return;
    }
    int m=(l+r)>>1;
    if(dly[rt])pushdown(rt);
    if(L<=m)updata(L,R,val,lson);
    if(R>m)updata(L,R,val,rson);
    pushup(rt,m);
}
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)return maxlen[rt];
    int m=(l+r)>>1;
    if(R<=m)return query(L,R,lson);
    if(L>m)return query(L,R,rson);
    int ret=max(query(L,R,lson),query(L,R,rson));
    if(valr[rt<<1]<vall[rt<<1|1])ret=max(ret,min(R,rmost[rt<<1|1])-max(L,lmost[rt<<1])+1);
    return ret;
}
int main()
{
    int i,j,k,n,m,t,cs;
    char op[55];
    scanf("%d",&t);
    for(cs=1;cs<=t;++cs)
    {
        scanf("%d%d",&n,&m);
        build(1,n,1);
        printf("Case #%d:
",cs);
        while(m--)
        {
            scanf("%s%d%d",op,&i,&j);
            if(op[0]=='q')printf("%d
",query(i,j,1,n,1));
            else
            {
                scanf("%d",&k);
                updata(i,j,k,1,n,1);
            }
        }
    }
    return 0;
}