1511: [POI2006]OKR-Periods of Words
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 351 Solved: 220
[Submit][Status][Discuss]
Description
一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串P是串A的前缀, 当且仅当存在串B, 使得 A = PB. 如果 P A 并且 P 不是一个空串,那么我们说 P 是A的一个proper前缀. 定义Q 是A的周期, 当且仅当Q是A的一个proper 前缀并且A是QQ的前缀(不一定要是proper前缀). 比如串 abab 和 ababab 都是串abababa的周期. 串A的最大周期就是它最长的一个周期或者是一个空串(当A没有周期的时候), 比如说, ababab的最大周期是abab. 串abc的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.
Input
第一行一个整数 k ( 1 k 1 000 000) 表示串的长度. 接下来一行表示给出的串.
Output
输出一个整数表示它所有前缀的最大周期长度之和.
Sample Input
8
babababa
babababa
Sample Output
24
题目大意：给定一个矩阵，初始每个位置上的元素都是0，每次选择一个子矩形，将这个子矩形内的值修改为这个子矩形内的最大值+h，
求最终所有位置上的最大
题解：维护一个数据结构标记永久化，二维线段树即可。
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<iostream> #define N 3007 #define Wb putchar(' ')
#define We putchar('\n')
#define rg register int
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
}
inline void write(int x)
{
if(x<) putchar('-'),x=-x;
if (x==) putchar();
int num=;char c[];
while(x) c[++num]=(x%)+,x/=;
while(num) putchar(c[num--]);
} int D,S,n;
int ql,qr,qd,qu; #define ls p<<1
#define rs p<<1|1
struct segx
{
int v[N],tag[N];
void change(int p,int l,int r,int x,int y,int z)
{
v[p]=max(v[p],z);
if (l==x&&y==r){tag[p]=max(tag[p],z);return;}
int mid=(l+r)>>;
if (y<=mid) change(ls,l,mid,x,y,z);
else if (x>mid) change(rs,mid+,r,x,y,z);
else change(ls,l,mid,x,mid,z),change(rs,mid+,r,mid+,y,z);
}
int query(int p,int l,int r,int x,int y)
{
if (l==x&&y==r) return v[p];
int mid=(l+r)>>,res=tag[p];
if (y<=mid) res=max(res,query(ls,l,mid,x,y));
else if (x>mid) res=max(res,query(rs,mid+,r,x,y));
else res=max(res,max(query(ls,l,mid,x,mid),query(rs,mid+,r,mid+,y)));
return res;
}
};
struct segy
{
segx v[N],tag[N];
void change(int p,int l,int r,int x,int y,int z)
{
v[p].change(,,S,qd,qu,z);
if (l==x&&y==r){tag[p].change(,,S,qd,qu,z);return;}
int mid=(l+r)>>;
if (y<=mid) change(ls,l,mid,x,y,z);
else if (x>mid) change(rs,mid+,r,x,y,z);
else change(ls,l,mid,x,mid,z),change(rs,mid+,r,mid+,y,z);
}
int query(int p,int l,int r,int x,int y)
{
if (l==x&&y==r) return v[p].query(,,S,qd,qu);
int mid=(l+r)>>,res=tag[p].query(,,S,qd,qu);
if (y<=mid) res=max(res,query(ls,l,mid,x,y));
else if (x>mid) res=max(res,query(rs,mid+,r,x,y));
else res=max(res,max(query(ls,l,mid,x,mid),query(rs,mid+,r,mid+,y)));
return res;
}
}T;
#undef ls
#undef rs int main()
{
D=read(),S=read(),n=read();
rg d,s,w,x,y;
for (rg i=;i<=n;i++)
{
d=read(),s=read(),w=read(),x=read(),y=read();
ql=x+,qr=x+d,qd=y+,qu=y+s;
int ans=T.query(,,D,ql,qr);
T.change(,,D,ql,qr,ans+w);
}
qd=,qu=S;
write(T.query(,,D,,D));
}