Another LCIS
Time Limit: 1000 ms Memory Limit: 65536 kB Solved: 111 Tried: 1673
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,...,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].
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
http://acm.uestc.edu.cn/problem.php?pid=1425
//本来吧、有了昨天的LCIS经验、这题很好解决的、就把代码稍微改了下、然后、然后、一直被RunTime Error
//一直不明白为什么、结果、居然是出入的时候的问题、不是说了是一个字符的吗？
//发现别人是用字符串读的、然后过了、然后我也凌乱了、、、
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define lson l,m,k<<1
#define rson m+1,r,k<<1|1
#define N 100010
using namespace std;
struct node
{
int lmax,rmax,max;
int lva,rva;
int len,add;
};
node st[N<<2];
void up(node &k,node &ls,node &rs)
{
k.lva=ls.lva;
k.rva=rs.rva;
if(ls.rva<rs.lva)
{
k.lmax=(ls.len==ls.lmax?ls.lmax+rs.lmax:ls.lmax);
k.rmax=(rs.len==rs.rmax?ls.rmax+rs.rmax:rs.rmax);
k.max=max(max(k.lmax,k.rmax),ls.rmax+rs.lmax);
k.max=max(max(ls.max,rs.max),k.max);
}
else
{
k.lmax=ls.lmax;
k.rmax=rs.rmax;
k.max=max(ls.max,rs.max);
}
}
void down(int &k)
{
st[k<<1].add+=st[k].add;
st[k<<1|1].add+=st[k].add;
st[k<<1].lva+=st[k].add;
st[k<<1].rva+=st[k].add;
st[k<<1|1].lva+=st[k].add;
st[k<<1|1].rva+=st[k].add;
st[k].add=0;
}
void build(int l,int r,int k)
{ // printf("%d ",k);
st[k].len=r-l+1;
st[k].add=0;
if(l==r)
{
scanf("%d",&st[k].lva);
st[k].rva=st[k].lva;
st[k].max=st[k].lmax=st[k].rmax=1;
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
int t=k<<1;
up(st[k],st[t],st[t+1]);
}
int va;
void updata(int &L,int &R,int l,int r,int k)
{
if(L<=l&&R>=r)
{
st[k].add+=va;
st[k].lva+=va;
st[k].rva+=va;
return ;
}
if(st[k].add)
down(k);
int m=(l+r)>>1;
if(L<=m) updata(L,R,lson);
if(R>m) updata(L,R,rson);
int t=k<<1;
up(st[k],st[t],st[t+1]);
}
node Query(int &L,int &R,int l,int r,int k)
{
if(L<=l&&R>=r)
return st[k];
if(st[k].add)
down(k);
int m=(l+r)>>1;
node r1,r2,temp;
r1.len=r2.len=0;
if(L<=m) r1=Query(L,R,lson);
if(R>m) r2=Query(L,R,rson);
if(r1.len&&r2.len)
{
up(temp,r1,r2);
temp.len=r1.len+r2.len;
return temp;
}
if(r1.len) return r1;
if(r2.len) return r2;
}
int main()
{
// freopen("in.txt","r",stdin);
int T,ct=1;
int n,m,x,y;//printf("%d\n",1<<20);
scanf("%d",&T);
node te;
char c[5];
while(T--)
{
scanf("%d%d",&n,&m);
build(1,n,1);
printf("Case #%d:\n",ct++);
while(m--)
{
//getchar();
scanf("%s",c);//就换了这的输入、、坑爹呀
if(c[0]=='q')
{
scanf("%d%d",&x,&y);
te=Query(x,y,1,n,1);
printf("%d\n",te.max);
}
else
{
scanf("%d%d%d",&x,&y,&va);
updata(x,y,1,n,1);
}
}
}
return 0;
}