hdoj3308 LCIS

单点修改的最长连续递增子序列
比前面几题都要简单,但是磨蹭了n久。。原因是query的时候没弄清楚,query的时候可能去左子区间也可能去右子区间,还有一种是答案是左右子区间拼起来的,想是想到了,但是还是写错了。。这种情况下应该是左起点选max(L,m+1-rmax[lson]),右起点选min(R,m+lmax[rson]).但是我原来写的时候只有当L<=m+1-rmax[lson] && m+lmax[rson]<=R的时候才考虑这种情况。。。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
#define maxn 100000
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int data[maxn+10];
int lmax[maxn<<2],rmax[maxn<<2],mmax[maxn<<2];
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	mmax[id]=max(mmax[lson],mmax[rson]);
	if(data[m]<data[m+1]) mmax[id]=max(mmax[id],rmax[lson]+lmax[rson]);
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl && data[m]<data[m+1]) lmax[id]=lenl+lmax[rson];
	if(rmax[rson]==lenr && data[m]<data[m+1]) rmax[id]=lenr+rmax[lson];
	return;
}
void build(int id,int l,int r)
{
	if(l==r)
	{
		lmax[id]=rmax[id]=mmax[id]=1;
		scanf("%d",&data[l]);
		return;
	}
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	pushup(id,l,r);
	return;
}
void update(int id,int l,int r,int pos,int v)
{
	if(l==r)
	{
		data[l]=v;return;
	}
	int m=(l+r)/2;
	if(pos<=m) update(lson,l,m,pos,v);
	else update(rson,m+1,r,pos,v);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return mmax[id];
	int m=(l+r)/2,ret=0;
	if(L<=m) ret=query(lson,l,m,L,R);
	if(R>m) ret=max(ret,query(rson,m+1,r,L,R));
	if(data[m]<data[m+1])
		ret=max(ret,min(m+lmax[rson],R)-max(m+1-rmax[lson],L)+1);
    return ret;
}
void debug(int id,int l,int r)
{
    printf("l:%d  r:%d  mmax:%d\n",l,r,mmax[id]);
    if(l==r) return;
    int m=(l+r)/2;
    debug(lson,l,m);
    debug(rson,m+1,r);
    return;
}
int main()
{
    //freopen("data.in","r",stdin);
	int i,j,t;
	int n,m;
	int a,b;
	char com[3];
	scanf("%d",&t);
	while(t–)
	{
		scanf("%d%d",&n,&m);
		build(1,0,n-1);
		for(i=1;i<=m;i++)
		{
			scanf("%s%d%d",com,&a,&b);
			if(com[0]==’U') update(1,0,n-1,a,b);
			else printf("%d\n",query(1,0,n-1,a,b));
		}
	}
	return 0;
}

poj3667 Hotel

经典的区间合并的线段树
关于找满足要求长度的最左连续空闲区:
维护左起连续空闲区lmax,右起连续空闲区rmax,区间最长连续空闲区max。当区间max=len,若是则转入左子区间,否则看rmax[lson]+lmax[rson]是否>=len,若是,则直接返回m+1-rmax[lson],若还是不行,则忘右区间找一定能找到(因为已经确定max[id]>=len)。
为什么这样是正确的?
如果最终答案不是lmax那段,也不是rmax那段,而是当前区间中间的一段空白,那么如果它被两个子区间隔开,那么必然是rmax[lson]+lmax[rson],否则它必定在左子区间或右子区间,这种情况下会继续往下找。知道所求区间是lmax或rmax或rmax[lson]+lmax[rson]或到达叶子结点。所以只设置这些量是足够的。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=50000;
int lmax[maxn<<2],max[maxn<<2],rmax[maxn<<2];
bool set[maxn<<2],reset[maxn<<2];
int maxlen(int a,int b,int c)
{
	int ret=a;
	if(b>ret) ret=b;
	if(c>ret) ret=c;
	return ret;
}
void do_set(int id,int l,int r)
{
	lmax[id]=rmax[id]=max[id]=0;
	set[id]=1;reset[id]=0;
	return;
}
void do_reset(int id,int l,int r)
{
	int len=r-l+1;
	lmax[id]=rmax[id]=max[id]=len;
	reset[id]=1;set[id]=0;
	return;
}
void pushup(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	lmax[id]=lmax[lson];
	rmax[id]=rmax[rson];
	if(lmax[lson]==lenl) lmax[id]=lenl+lmax[rson];
	if(rmax[rson]==lenr) rmax[id]=lenr+rmax[lson];
	max[id]=maxlen(lmax[id],rmax[id],rmax[lson]+lmax[rson]);
	max[id]=maxlen(max[id],max[lson],max[rson]);
	return;
}
void pushdown(int id,int l,int r)
{
	int m=(l+r)/2;
	int lenl=m-l+1,lenr=r-m;
	if(reset[id])
	{
		lmax[lson]=rmax[lson]=max[lson]=lenl;reset[lson]=1;set[lson]=0;
		lmax[rson]=rmax[rson]=max[rson]=lenr;reset[rson]=1;set[rson]=0;
		reset[id]=0;
	}
	if(set[id])
	{
		lmax[lson]=rmax[lson]=max[lson]=0;set[lson]=1;reset[lson]=0;
		lmax[rson]=rmax[rson]=max[rson]=0;set[rson]=1;reset[rson]=0;
		set[id]=0;
	}
	return;
}
void build(int id,int l,int r)
{
	set[id]=reset[id]=0;
	lmax[id]=rmax[id]=max[id]=r-l+1;
	if(l==r) return;
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	return;
}
void update(int id,int l,int r,int L,int R,int type)
{
	if(L<=l && r<=R)
	{
		if(type==0) do_reset(id,l,r);
		else do_set(id,l,r);
		return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,type);
	if(R>m) update(rson,m+1,r,L,R,type);
	pushup(id,l,r);
	return;
}
int query(int id,int l,int r,int len)
{
	if(max[id]<len) return 0;
	if(l==r) return l;
	pushdown(id,l,r);
	int m=(l+r)/2;
	if(max[lson]>=len) return query(lson,l,m,len);
	if(rmax[lson]+lmax[rson]>=len) return m+1-rmax[lson];
	return query(rson,m+1,r,len);
}
void debug(int id,int l,int r)
{
	if(l==r)
	{
		printf("%d ",1-max[id]);return;
	}
	pushdown(id,l,r);
	int m=(l+r)/2;
	debug(lson,l,m);
	debug(rson,m+1,r);

}
int main()
{
	int i,j;
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		build(1,1,n);
		for(i=1;i<=m;i++)
		{
			int c,a,b;
			scanf("%d",&c);
			if(c==1)
			{
				scanf("%d",&a);
				int pos=query(1,1,n,a);
				if(pos) update(1,1,n,pos,pos+a-1,1);
				printf("%d\n",pos);
				//debug(1,1,n);printf("\n");
				//printf("max[1]:%d\n",max[1]);
			}
			else
			{
				scanf("%d%d",&a,&b);
				update(1,1,n,a,a+b-1,0);
				//debug(1,1,n);printf("\n");
			}
		}
	}
	return 0;
}

poj2991 Crane——线段转化成向量,向量旋转

神奇的一道题,解法很奇妙————对我而言。。
题意:给出一些线段,起始时它们一次邻接的排列在二维笛卡尔坐标系上,端点分别是(0,w1)(0,w1+w2)……(0,w1+w1+……+wn),wi是第i个线段的长度。给出一些操作s,angle。表示把第s条线段的右端点p的后面的所有线段以p为中心旋转到p点两侧的线段成angle角度。(angle角度=以线段s以p点为中心逆时针转到与线段s+1重合经过的角度),要求每次操作后输出线段n右端点的坐标。
难点:直接做很麻烦,因为每次旋转的中心点可能不同,操作无法统一化表示,如果能统一化的话,就可以使用线段树了。
关键点:
1.把线段看成向量。
2.当进行操作是s,angle后,第s+1条线段开始的线段所在直线都旋转了angle角度。
3.向量(x1,y2)逆时针旋转a弧度后的端点坐标为
x1=x0*cos(a)-y0*sin(a);
y1=x0*sin(a)+y0*cos(a);
当顺时针旋转b弧度时,a=-b。相当与旋转了负角度。

有了这三个认识,题目就简单了。线段树中的结点(id,l,r)存储的是第l条线段的右端点到第r条线段的右端点表示的向量的右端点的横纵坐标。所以其实答案就是(x[1],y[1])。
那么怎样把题目告诉的旋转到成angle角度转化为旋转了多少角度呢?
这个简单,只要开个数组angle[],angle[i]表示第i条和第i+1条线段现在所成的角度。那么假如现在要旋转到成r弧度角,那么旋转了r-angle[i].注意化成弧度计算哦。

#include<stdio.h>
#include<string.h>
#include<math.h>
#define lson id<<1
#define rson id<<1|1
#define maxn 10000
const double eps=1e-8;
const double pi=acos((double)(-1.0));
double len[maxn+10],angle[maxn+10];
double x[maxn<<2],y[maxn<<2],rotate[maxn<<2];
double radio(double ang){return (ang*pi)/180;}
void change(double &x,double &y,double ang)
{
	double xx=x,yy=y;
	x=xx*cos(ang)-yy*sin(ang);
	y=xx*sin(ang)+yy*cos(ang);
	return;
}
void pushup(int id)
{
	x[id]=x[lson]+x[rson];
	y[id]=y[lson]+y[rson];
	return;
}
void pushdown(int id)
{
	if(fabs(rotate[id]-0)<eps) return;
	change(x[lson],y[lson],rotate[id]);rotate[lson]+=rotate[id];
	change(x[rson],y[rson],rotate[id]);rotate[rson]+=rotate[id];
	rotate[id]=0;
	return;
}
void build(int id,int l,int r)
{
	rotate[id]=0;
	if(l==r)
	{
		x[id]=0;y[id]=len[l];
		return;
	}
	int m=(l+r)/2;
	build(lson,l,m);
	build(rson,m+1,r);
	pushup(id);
	return;
}
void update(int id,int l,int r,int L,int R,double rad)
{
	if(L<=l && r<=R)
	{
		change(x[id],y[id],rad);
		rotate[id]+=rad;
		return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,rad);
	if(R>m) update(rson,m+1,r,L,R,rad);
	pushup(id);
	return;
}
int main()
{
	int i,j;
	int n,m;
	bool flag=1;
	while(~scanf("%d%d",&n,&m))
	{
		for(i=1;i<=n;i++) scanf("%lf",&len[i]);
		for(i=1;i<=n;i++) angle[i]=pi;
		int s;
		double ang;
		build(1,1,n);
		if(flag) flag=0;
		else printf("\n");
		for(i=1;i<=m;i++)
		{
			scanf("%d%lf",&s,&ang);
			double r=radio(ang)-angle[s];
			update(1,1,n,s+1,n,r);
			angle[s]=radio(ang);
			printf("%.2f %.2f\n",x[1],y[1]);
		}
	}
	return 0;
}

poj1436 Horizontally Visible Segments

终于ac了,不容易啊。。
题意:给出n条垂直的不相交线段,如果两条线段之间可以用一条不穿过其他线段的水平线段连接起来,那么称这两条线段互相可见。如果三条线段间两两可见,那么称这三条线段组成三角形,问总共有多少个三角形。
思路:每条线段的id(将线段按x坐标排序,id从1开始)作为颜色,用线段树维护区间的颜色。每次插入一条线段,就询问这段区间内有哪些颜色(也就是之前插入的哪些线段与当前线段互相可见),之后更新该区间的颜色。起始时整个区间颜色为0,当一段区间内有多种颜色时color设成-1。
注意一点:
| | |
| |
| | |
1 2 3
上图中x坐标=2的两条线段的y坐标分别为(1,2)(3,4),那么显然线段1和3是互相可见的,但是因为在线段树上插入线段3时[1,4]这个区间颜色全是2,所以会会认为线段3与1不是互相可见。这样就造成了漏数。
解决:方法是线段树的每个点乘2.这样x、x+1变成2x、2x+2,中间的2x+1这个点就可以表示区间(x,x+1).

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<set>
#include<vector>
#define lson id<<1
#define rson id<<1|1
using namespace std;
const int maxn=8000*2;
int color[maxn<<2];
bool lazy[maxn<<2];
typedef struct Seg{
	int x,y1,y2;
}Seg;
Seg seg[maxn/2+10];
set<int> s[maxn/2+10];
set<int>::iterator it;
vector<int> map[maxn/2+10];
int cur;
bool cmp(Seg a,Seg b){return a.x<b.x;}
void pushup(int id)
{
	if(color[lson]!=color[rson]) color[id]=-1;
	else color[id]=color[lson];
	return;
}
void pushdown(int id)
{
	if(!lazy[id] || color[id]==-1 || color[id]==0) return;
	lazy[id]=0;
	color[lson]=color[id];lazy[lson]=1;
	color[rson]=color[id];lazy[rson]=1;
	return;
}
void update(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R)
	{
        color[id]=cur;
		lazy[id]=1;
		return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R);
	if(R>m) update(rson,m+1,r,L,R);
	pushup(id);
	return;
}
void query(int id,int l,int r,int L,int R)
{
	if(color[id]==0) return;
	if(L<=l && r<=R && color[id]!=-1)
	{
		s[cur].insert(color[id]);
		return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) query(lson,l,m,L,R);
	if(R>m) query(rson,m+1,r,L,R);
	return;
}
int main()
{
	int t,n;
	int i,j,k;
	int x,y1,y2;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int maxd=-1;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d",&seg[i].y1,&seg[i].y2,&seg[i].x);
			seg[i].y1*=2;seg[i].y2*=2;
			if(seg[i].y2>maxd) maxd=seg[i].y2;
		}
		sort(seg+1,seg+1+n,cmp);
		for(i=1;i<=n;i++)
		{
			if(!s[i].empty()) s[i].clear();
			if(!map[i].empty()) map[i].clear();
		}
		memset(color,0,sizeof(color));
		memset(lazy,0,sizeof(lazy));
		for(i=1;i<=n;i++)
		{
			cur=i;
			query(1,0,maxn,seg[i].y1,seg[i].y2);
			update(1,0,maxn,seg[i].y1,seg[i].y2);
		}
		for(i=1;i<=n;i++)
		{
			for(it=s[i].begin();it!=s[i].end();it++)
				map[i].push_back(*it);
		}
		int ans=0;
		for(i=1;i<=n;i++)
		{
			for(j=0;j<map[i].size();j++)
				for(k=j+1;k<map[i].size();k++)
				{
					int a=map[i][j],b=map[i][k];
					if(a>b) {a^=b;b^=a;a^=b;}
					if(s[b].find(a)!=s[b].end()) ans++;
				}
		}
		printf("%d\n",ans);
	}
	return 0;
}

poj3225 Help with Intervals——线段树

开始对于区间乘以2的方法没理解透彻导致错误。
由于涉及开闭区间,所以既要用到点又要用到区间。普通线段树实际上是将区间堪看成离散的点,每次操作都是对点进行操作,对连续的区间则无可奈何。
解决方法:对于数x,x乘2,2x表示点本身,2x+1表示(x,x+1)这段区间。这样问题就解决了。

#include<stdio.h>
#include<string.h>
#define lson id<<1
#define rson id<<1|1
const int maxn=(65535<<1|1);
bool set[4*maxn],reset[4*maxn],rev[4*maxn];
int a[maxn+10];
void do_set(int id) {set[id]=1;reset[id]=rev[id]=0;}
void do_reset(int id) {reset[id]=1;set[id]=rev[id]=0;}
void do_rev(int id)
{
	if(set[id]==1) {do_reset(id);return;}
	if(reset[id]==1) {do_set(id);return;}
	rev[id]^=1;return;
}
void do_it(int id,int type)
{
	if(type==1) do_set(id);
	if(type==2) do_reset(id);
	if(type==3) do_rev(id);
}
void pushdown(int id)
{
	if(set[id]) {do_set(lson);do_set(rson);}
	if(reset[id]) {do_reset(lson);do_reset(rson);}
	if(rev[id]) {do_rev(lson);do_rev(rson);}
	set[id]=reset[id]=rev[id]=0;
}
void update(int id,int l,int r,int L,int R,int type)
{
    if(L>R || L<0) return;
	if(L<=l && r<=R)
	{
		do_it(id,type);return;
	}
	pushdown(id);
	int m=(l+r)/2;
	if(L<=m) update(lson,l,m,L,R,type);
	if(R>m) update(rson,m+1,r,L,R,type);
	return;
}
void out(int id,int l,int r)
{
	if(l==r)
	{
		if(set[id] || rev[id]) {a[l]=1;return;}
		if(reset[id]) {a[l]=0;return;}
		a[l]=0;return;
	}
	pushdown(id);
	int m=(l+r)/2;
	out(lson,l,m);
	out(rson,m+1,r);
}
int main()
{
	int i,j;
	char com[5],left,right;
	int l,r;
	memset(set,0,sizeof(set));
	memset(reset,0,sizeof(reset));
	memset(rev,0,sizeof(rev));
	while(~scanf("%s %c%d,%d%c",com,&left,&l,&r,&right))
	{
	    getchar();
		if(left=='[') l<<=1;
		else l=(l<<1|1);
		if(right==')') r=(r<<1)-1;
		else r=(r<<1);
		if(com[0]=='U') update(1,0,maxn,l,r,1);
		if(com[0]=='I') {update(1,0,maxn,0,l-1,2);update(1,0,maxn,r+1,maxn,2);}
		if(com[0]=='D') update(1,0,maxn,l,r,2);
		if(com[0]=='C') {update(1,0,maxn,0,l-1,2);update(1,0,maxn,r+1,maxn,2);update(1,0,maxn,l,r,3);}
		if(com[0]=='S') update(1,0,maxn,l,r,3);
	}
	out(1,0,maxn);
	bool flag=1;
	for(i=0;i<=maxn;i++)
	{
		if(((a[i]==1) && (i==0)) || ((a[i]==1) && (a[i-1]==0)))
		{
			if(!flag) printf(" ");
			else flag=0;
			if(i&1) printf("(%d,",i/2);
			else printf("[%d,",i/2);
		}
		if(((a[i]==1) && (i==maxn)) || ((a[i]==1) && (a[i+1]==0)))
		{
			if(i&1) printf("%d)",i/2+1);
			else printf("%d]",i/2);
		}
	}
	if(flag) printf("empty set");
	printf("\n");
	return 0;
}

hdoj3874 Necklace——线段树离线处理

好久没做题,刷下存在感。。
线段树题,问[l,r]之间数的和,同样的数只算一遍。
思路:把询问离线保存下来,按右端点排序,用hash[x]表示数x到目前为止出现的最右位置。如果x以前出现过,则把位置hash[x]处清零,然后当前位置置为x。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson id<<1
#define rson id<<1|1
#define maxn 50000+10
using namespace std;
typedef __int64 ll;
int n,m;
ll sum[4*maxn],ans[200000+10];
typedef struct Q{
	int l,r;
	int num;
}Q;
Q q[200000+10];
int hash[1000000+10];
void pushup(int id)
{
	sum[id]=sum[lson]+sum[rson];
	return;
}
void update(int id,int l,int r,int pos,ll v)
{
	if(l==r)
	{
		sum[id]=v;return;
	}
	int m=(l+r)/2;
	if(pos<=m) update(lson,l,m,pos,v);
	else update(rson,m+1,r,pos,v);
	pushup(id);
	return;
}
ll query(int id,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return sum[id];
	int m=(l+r)/2;
	ll ret=0;
	if(L<=m) ret+=query(lson,l,m,L,R);
	if(R>m) ret+=query(rson,m+1,r,L,R);
	return ret;
}
bool cmp(Q a,Q b)
{
	return a.r<b.r;
}
bool cmp2(Q a,Q b)
{
	return a.num<b.num;
}
ll a[maxn];
int main()
{
	int i,j,k,t;
	scanf("%d",&t);
	while(t--)
	{
		memset(hash,0,sizeof(hash));
		memset(sum,0,sizeof(ll)*(4*n+5));
		scanf("%d",&n);//scanint(n);
		for(i=1;i<=n;i++) scanf("%I64d",&a[i]);//scanll(a[i]);
		scanf("%d",&m);//scanint(m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&q[i].l,&q[i].r);//scanint(q[i].l);scanint(q[i].r);
			q[i].num=i;
		}
		sort(q+1,q+1+m,cmp);
		k=0;
		for(i=1;i<=m;i++)
		{
			for(j=k+1;j<=q[i].r;j++)
			{
				if(!hash[a[j]])
				{
					hash[a[j]]=j;
					update(1,1,n,j,a[j]);
				}
				else
				{
					update(1,1,n,hash[a[j]],0);
					hash[a[j]]=j;
					update(1,1,n,j,a[j]);
				}
			}
			k=q[i].r;
			ans[q[i].num]=query(1,1,n,q[i].l,q[i].r);
		}
		for(i=1;i<=m;i++)
			printf("%I64d\n",ans[i]);
	}

	return 0;
}

cf371D Vessels

不知道哪错了,待改。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define lson id<<1
#define rson id<<1|1
typedef long long ll;
const int maxn=2e5+10;
ll a[4*maxn],sum[4*maxn];
bool lazy[4*maxn];
int n,m;
void pushup(int id)
{
    sum[id]=sum[lson]+sum[rson];return;
}
void pushdown(int id)
{
    if(!lazy[id]) return;
    sum[lson]=0;lazy[lson]=1;
    sum[rson]=0;lazy[rson]=1;
    lazy[id]=0;
    return;
}
void build(int id,int l,int r)
{
    if(l==r)
    {
        scanf("%I64d",&a[id]);
        sum[id]=a[id];
        return;
    }
    int m=(l+r)/2;
    build(lson,l,m);
    build(rson,m+1,r);
    pushup(id);
    return;
}
void update(int id,int l,int r,int L,int R)
{
    if(L>R) return;
    if(L<=l && r<=R)
    {
        sum[id]=0;lazy[id]=1;
        return;
    }
    pushdown(id);
    int m=(l+r)/2;
    if(L<=m) update(lson,l,m,L,R);
    if(R>m) update(rson,m+1,r,L,R);
    pushup(id);
    return;
}
void update2(int id,int l,int r,int pos,ll v)
{
    if(l==r)
    {
        sum[id]-=v;
        if(sum[id]<0) sum[id]=0;
        return;
    }
    pushdown(id);
    int m=(l+r)/2;
    if(pos<=m) update2(lson,l,m,pos,v);
    else update2(rson,m+1,r,pos,v);
    pushup(id);
    return;
}
ll query_sum(int id,int l,int r,int L,int R)
{
    if(L>R) return 0;
    if(L<=l && r<=R)
    {
        return sum[id];
    }
    pushdown(id);
    int ret=0,m=(l+r)/2;
    if(L<=m) ret+=query_sum(lson,l,m,L,R);
    if(R>m) ret+=query_sum(rson,m+1,r,L,R);
    return ret;
}
ll query(int id,int l,int r,int pos)
{
    if(l==r)
    {
        return a[id]-sum[id];
    }
    pushdown(id);
    int m=(l+r)/2;
    if(pos<=m) return query(lson,l,m,pos);
    else return query(rson,m+1,r,pos);
}
int bsearch(int pos,int l,int r,ll v)
{
    int mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(query_sum(1,1,n,pos,mid)<v) l=mid+1;
        else r=mid-1;
    }
    return l;
}
void debug(int id,int l,int r)
{
    if(l==r)
    {
        printf("%d ",sum[id]);
        return;
    }
    int m=(l+r)/2;
    debug(lson,l,m);
    debug(rson,m+1,r);
    return;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        memset(lazy,0,sizeof(lazy));
        int com,p;
        ll x;
        build(1,1,n);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d",&com);
            if(com==1)
            {
                scanf("%d%I64d",&p,&x);
                int ret=bsearch(p,p,n,x);
                ll tmp=query_sum(1,1,n,p,ret-1);
                update(1,1,n,p,ret-1);
                update2(1,1,n,ret,x-tmp);
                //debug(1,1,n);puts("");
            }
            else
            {
                scanf("%d",&p);
                printf("%I64d\n",query(1,1,n,p));
                //debug(1,1,n);puts("");
            }
        }
    }
    return 0;
}

round#215 div2

昨晚第一次做cf,结果做了两题就笔记本断电滚粗了。。
A Sereja and Coat Rack 水题
B Sereja and Suffixes 预处理
C Sereja and Algorithm
题意:给出长度<=1e5的字符串s(只含有xyz),给出算法:随意选三个字母长的子串,且要求它不是xzy、yxz、zyx三个中的一个,然后可以随意重排它。直到找不出这样的三字母长的子串,算法结束。对于每个样例,给出m个询问(m<=1e5):l r。问s[l……r]能否在有限步数内终结。
思路:可知如果会终结,则最后的字符串一定是以下情况中的一种:
(1)形如xzyxzy……或者yxzyxz……或者zyxzyx……
(2)只有一个字母或两个字母。
注意第(2)种情况,被坑了。。
所以预处理统计符合条件的长度为i的字符串中x、y、z各自的个数即可(三种情况),然后统计s[l……r]中x、y、z的个数
D:现在还不会。。。。。。。
E Sereja and the Arrangement of Numbers
题意:给出n(n<=2*1e6),m(m<=1e5),给出m个互异的整数。定义数列:a1、a2……an,如果任意两个数ai、aj(ai!=aj)存在pos(1<=pos<=n),a[pos]=ai,a[pos+1]=aj或者a[pos]=aj,a[pos+1]=ai,则称该数列合法。给出的m个数有各自的价值,问组成长度为n的合法数列最多能得到价值。
看了题解才知道是图论,,弱爆了。。
先求出i个不同的数组成合法序列的最小长度。然后对于n只要在这个数组(已经单调)中二分出它的位置pos,pos表示组成长度为n的合法序列最多可以用多少个不同的数。然后将给出的m个数降序排列,取前面pos个。
关键在于求出i个不同的数组成合法序列的最小长度:
方法是可以把i个不同的数看成i个点,两两之间连边形成完全图。有边表示两点相邻。问题变为求最小加多少条边可以使其变成半欧拉图。(因为如果是半欧拉图的话,就可以不重复的遍历所有边,也就是找到了一个序列满足所有相邻关系)。分奇偶讨论,偶数要加n/2-1,因为i为偶数的话,每个点的度数是奇数,最后要补成只有两个奇度点。注意序列长度=边数+1;

polya定理&&burnside引理

专题地址:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=36645#overview
这里有更完整的:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=484
看了下大白书,做下上面的习题。两个定理叙述很简单,证明暂时没看,先把题做的差不多再说。。
一些小结:
1.置换。一对一的函数
2.置换的乘法:满足结合律,但不满足交换律
3.置换分解成几个循环的乘积,因为假如将一个置换看成一条有向边那么形成的图中每个点都是入度为1,出度为1.所以一定是若干个圈。
4.独立的循环之间的乘法满足交换律
5.设A是与元素个数为n的循环,则:
(1)若n为奇数,则A*A是一个n个元素的循环
(2)若n为偶数,则A*A是两个n/2个元素且相互独立的循环的乘积
6.引出:由5的性质可知:
(1)一个长度n为奇数的循环B,一定可以找到一个长度为n的循环A,满足A^2=B;
(2)两个长度都为n的不相交循环B和C,一定可以找到长度为2*n的循环A,使得A^2=B*C;
7.继续引出:
(1)长度n为奇数的循环既可以是两个长度为n的循环乘出来的,也可以是两个长度为2n的循环乘出来的。
(2)长度n为偶数的循环只可能是两个长度为2n的循环乘出来的。
下面是一些题目
UVA 10294 Arif in Dhaka (First Love Part 2)
数学推算。。

#include<stdio.h>
#include<math.h>
typedef long long ll;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
ll fact[15][60];
int main()
{
	int i,j;
	int n,t;
	for(i=1;i<=10;i++)
		fact[i][1]=(ll)i;
	for(i=1;i<=10;i++)
		for(j=2;j<=50;j++)
			fact[i][j]=fact[i][j-1]*(ll)i;
	while(~scanf("%d%d",&n,&t))
	{
		ll a=0,b=0;
		for(i=0;i<=n-1;i++)
			a+=fact[t][gcd(n,i)];
		b=n*(fact[t][(n+1)/2]+fact[t][(n+2)/2])/2;
		printf("%lld ",a/n);
		printf("%lld\n",(a+b)/(2*n));
	}
	return 0;
}

UVALive 3641 Leonardo’s Notebook
上述的几点“引出”。。

#include<stdio.h>
#include<string.h>
char s[30];
int ring[30];
bool visit[30];
int dfs(int cur)
{
	int ret=1;
	if(visit[cur]) return 0;
	visit[cur]=1;
	ret+=dfs(s[cur]-'A'+1);
	return ret;
}
int main()
{
	int i,j;
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s+1);
		memset(ring,0,sizeof(ring));
		memset(visit,0,sizeof(visit));
		for(i=1;i<=26;i++)
		{
			if(visit[i]) continue;
			int ret=dfs(i);
			ring[ret]++;
		}
		for(i=1;i<=26;i++)
			if(!(i&1) && ring[i]&1) break;
		if(i<=26) printf("No\n");
		else printf("Yes\n");
	
	}
	return 0;
}

UVA 11077 Find the Permutations
递推,具体见lrj的训练指南。

#include<stdio.h>
#include<string.h>
typedef unsigned long long ll;
ll f[22][22];
int main()
{
	int i,j;
	int n,k;
	memset(f[1],0,sizeof(f[1]));
	f[1][0]=1;
	for(i=2;i<=21;i++)
		for(j=0;j<i;j++)
		{
			if(j==0) f[i][j]=1;
			f[i][j]=f[i-1][j]+f[i-1][j-1]*(i-1);
		}
	while(~scanf("%d%d",&n,&k) && !(n==0 && k==0))
		printf("%llu\n",f[n][k]);
	return 0;
}

2013 hangzhou regional I题

感觉最近写代码总是小错误不断,没有刚学acm时认真了。。

#include<stdio.h>
#include<string.h>
int box[30][10];
int dp[1<<21];
int g,b,s,goal;
inline int max(int a,int b){return a>b?a:b;}
int DP(int st)
{
    int i,j,k;
    if(dp[st]!=-1) return dp[st];
    int co[10];
    memset(co,0,sizeof(co));
    for(i=0;i<=b-1;i++)
    {
        if(!(st&(1<<i))) continue;
        for(j=1;j<=g;j++) co[j]+=box[i][j];
    }
    int sr=0;
    for(i=1;i<=g;i++)
    {
        sr+=co[i]/s;
        co[i]=co[i]%s;
    }
    int rest=goal-sr;
    for(i=0;i<=b-1;i++)
    {
        if(st&(1<<i)) continue;
        int score=0,tmpc[10];
        for(j=1;j<=g;j++) tmpc[j]=co[j];
        for(j=1;j<=g;j++)
        {
            tmpc[j]+=box[i][j];
            score+=tmpc[j]/s;
        }
        if(score)
        {
            dp[st]=max(dp[st],score+DP(st|(1<<i)));
        }
        else
        {
            dp[st]=max(dp[st],rest-DP(st|(1<<i)));
        }
    }
    return dp[st];
}
int main()
{
    int i,j;

    while(~scanf("%d%d%d",&g,&b,&s) && !(g==0 && b==0 && s==0))
    {
        memset(dp,-1,sizeof(dp));
        memset(box,0,sizeof(box));
        dp[(1<<b)-1]=0;
        for(i=0;i<=b-1;i++)
        {
            int n;
            scanf("%d",&n);
            for(j=1;j<=n;j++)
            {
                int c;
                scanf("%d",&c);
                box[i]1++;
            }
        }
        goal=0;
        int col[10];memset(col,0,sizeof(col));
        for(i=0;i<=b-1;i++)
            for(j=1;j<=g;j++)
                col[j]+=box[i][j];
        for(j=1;j<=g;j++)
            goal+=col[j]/s;
        printf("%d\n",2*DP(0)-goal);
    }
    return 0;
}

uva12589 Learning Vector

比赛的时候没想到是背包的dp啊。。。
思路:先按斜率排序,因为对于确定的一些向量,一定是斜率大的在前可以使总面积最大化。dp方程主体是背包,但是加了一维,表示最右侧的向量的最高点的y值。也就是dp[i][j][k]表示前i个向量中选取j个且最右侧高为k的最大面积。可以用滚动数组省掉阶段那一维,然后和一般背包不同的是,因为如果填表的话,每次对于dp[i][j][k],都要枚举dp[i-1][j-1][0……k-1],复杂度很高,所以用刷表的方式,每次用dp[i][j][k]更新dp[i+1][j+1][k+p[i].y]。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef struct Point{
    int x,y;
}Point;
Point p[60];
bool cmp(Point a,Point b)
{
    return a.y*b.x>b.y*a.x;
}
int dp[60][3000];
int main()
{
    int i,j,r,cases=0;
    int t,n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        memset(dp,-inf,sizeof(dp));dp[0][0]=0;
        for(i=1;i<=n;i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        sort(p+1,p+1+n,cmp);
        for(i=1;i<=n;i++)
        {
            for(j=k;j>=0;j--)
            {
                for(r=0;r<=50*n;r++)
                {
                    if(dp[j][r]==-inf) continue;
                    int tmp=dp[j][r]+(r+p[i].y+r)*p[i].x;
                    if(tmp>dp[j+1][r+p[i].y])
                        dp[j+1][r+p[i].y]=tmp;
                }
            }
        }
        int ans=-inf;
        for(r=0;r<=50*n;r++) if(dp[k][r]>ans) ans=dp[k][r];
        printf("Case %d: %d\n",++cases,ans);

    }
    return 0;
}

splay tree专题

很早以前就想学splay,但是迫于图论方面的知识还很不全面,于是放弃了计划,第一次区域赛之后打算学一下splay,所以这几天就开始看起来了,看着爽哥的ppt和模板慢慢学,到现在为止基本上理解了splay树的旋转和splay操作,然后就开始做题啦。。接下来要开始重点转入dp和数据结构的学习了~
1.关于rotate和splay操作的一个问题:为什么旋转x结点的时候只pushup()fa[x]?
答:因为rotate操作是用在splay操作里面的,由于splay的时候x结点可能被旋转多次,所以x结点为根的子树的结构在不停变化中,没必要每次旋转都pushup,但是旋转点x的父亲结点却在旋转后不会再旋转了,所以要pushupx结点的父亲。最后全部旋转完毕在pushupx结点就行了。
2.由此可能想到另一个问题:splay的时候,又是旋转x结点前要先旋转x的父节点y,这时候pushup了y的父节点z,那么y结点有没有pushup呢?
答:有的,因为每次旋转y必然伴随着旋转一次x,所以旋转x的时候,y结点pushup了。
3.要注意哪些地方要pushdown。旋转一个节点前要先pushdown父节点,再pushdownx节点,将信息下推,完成这个节点的”使命”再旋转。访问一个节点的操作之前记得pushdown,再对这个节点操作。
4.深刻理解splay树的“序”:这个序是很广义的,没有序也可以是序。加入初始插入节点完毕时其实就形成了一个“序”。这时它的中序遍历序列就是它的序,也就是说此时splay中的任意两个元素间有了一种前后关系,这就是序。splay操作会维护splay树的平衡但是不会改变这个序,也就是说splay操作之后树的中序遍历序列式不变的。
5.findpre(x)和findnext(x):这两个操作必须先把x节点splay到根。因为如果不是根,那么x的父节点有可能是所求答案,但是findpre()和findnext()并没有考虑
6.关于翻转操作

void rever(int x)
    {
        swap(LC,RC);
        rev[x]^=1;//为什么不是rev[x]=1;因为可能原来rev[x]就是1,表示这棵子树翻转过了,所以现在再翻一次,之后rev[x]^=1,rev[x]=0了,表示这棵树不用翻转了,也就不用向下传递标记了。
        return;
    }

 
hdoj1754 I Hate It
单点更新,区间询问最值

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 200000+5
#define inf 0x3f3f3f3f
inline int max(int a,int b){return a>b?a:b;}
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]

	int root;//根节点
	int fa[N];//父亲结点
	int ch[N][2];//孩子结点
	int sz[N];//以结点i为子树的结点数
	int top1;//曾经用过的结点
	int top2;//可用结点栈的栈顶
	int ss[N];//可用结点栈
	int que[N];//回收节点用到的队列
	int num[N];//结点的权值
	int val[N];//结点的值
	int maxvalue[N];//区间最大值
	int nodeNum;

	void pushup(int x)
	{
		sz[x]=1+sz[LC]+sz[RC];//如果左子树为空,则LC=0,而sz[0]=0,即如果结点某个结点的子节点不存在,则指向空结点0,空节点的sz=0,不会造成错误
		maxvalue[x]=max(maxvalue[LC],maxvalue[RC]);
		maxvalue[x]=max(maxvalue[x],val[x]);
	}

	void rotate(int x, bool f) //旋转
	{
		int y=fa[x];
		int z=fa[y];
		ch[y][!f]=ch[x][f];
		fa[ch[x][f]]=y;
		fa[x]=z;
		if(z)
		{
			ch[z][ch[z][1]==y]=x;
		}
		ch[x][f]=y;
		fa[y]=x;
		pushup(y);
	}

	void splay(int x, int g) //把结点x转到结点g下
	{
		int y=fa[x];
        while (y!=g)
        {
			int z=fa[y];
			bool f=(ch[y][0]==x);
			if (z!=g && f==(ch[z][0]==y))
			{
				rotate(y,f);
			}
			rotate(x,f);
			y=fa[x];
		}
		pushup(x);
		if(g==0)
		{
			root=x;
		}
	}

	void rotateto(int k,int g) {	//把第k个结点转到结点g下,从第0个开始,因为有附加结点
		int x=root;
		while (sz[LC]!=k)
		{
			if (k<sz[LC])
			{
				x=LC;
			} else
			{
				k-=(sz[LC]+1);
				x=RC;
			}
		}
		splay(x,g);
	}

	void newNode(int &x,int c)
	{
		if (top2)
		{//ss栈是存储删掉的结点,这些结点可用,如果该栈不空,直接用这里面的结点号
			x=ss[--top2];
		}
		else
		{
			x=++top1;//如果没有可用结点,则增加结点数。
		}
		LC=RC=fa[x]=0;
		sz[x]=1;
		val[x]=c;
		maxvalue[x]=c;
	}

	void makeTree(int &x,int l,int r,int f)
	{
		if (l>r)
		{
			return;
		}
		int m=(l+r)>>1;
		newNode(x,num[m]);	/*num[m]权值改成题目所需的*/
		makeTree(LC,l,m-1,x);
		makeTree(RC,m + 1,r,x);
		fa[x]=f;
		pushup(x);//建立树的时候,从下往上依次pushup
	}
	void init(int n)
	{
		nodeNum=n;
		ch[0][0]=ch[0][1]=fa[0]=sz[0]=0;//0结点是空节点,代表没有
		maxvalue[0]=-inf;
		root=top1=top2=0;
		//为了方便处理边界,加两个边界顶点
		newNode(root,-inf);
		newNode(ch[root][1],-inf);//这两个边界结点的值不影响正常求解
		fa[top1]=root;
		sz[root]=2;
		makeTree(KT,1,n,ch[root][1]);
		pushup(ch[root][1]);
		pushup(root);
	}

	//返回区间[l, r]中的最大值
	int query(int l,int r)
	{
		rotateto(l-1,0);
		rotateto(r+1,root);
		return maxvalue[KT];
	}
	void update(int id,int v)
	{
        rotateto(id-1,0);
        rotateto(id+1,root);
        int x=ch[root][1];
        maxvalue[LC]=val[LC]=v;
        pushup(x);
        pushup(root);
        return;
	}
}spt;
int main()
{
    int i,j;
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            scanf("%d",&spt.num[i]);
        spt.init(n);
        char com[5];
        int a,b;
        while(m--)
        {
            scanf("%s%d%d",com,&a,&b);
            if(com[0]=='U') {spt.update(a,b);continue;}
            printf("%d\n",spt.query(a,b));
        }
    }
    return 0;
}

hdoj1890 Robotic Sort
题意:一个序列,要对其排序,排序方法是:
第一轮从[1,n]中找到最小值的下标id,旋转序列[1,id],这时候第一个数已经是最小数了。
第二轮从[2,n]中找到最小值的下标id,旋转序列[2,id],这时候第二个数已经是第二小数了。
……
(以此类推)
第n轮从[n,n]中找到最小值的下标id,旋转序列[n,id],这时候第n个数已经是最小数了。
如果两个数相等,那么在排完序之后,原来下标小的仍然在前面,即这个排序过程是稳定的
思路:因为有重复值,而相等的数按排序时要按下标排,所以可以在插入splay之前先将这n个数hash成1~n这n个数,这样就避免了重复值得问题。
涉及splay的区间最小值和区间旋转,以及找到区间最小值的下标,显然按下标建树

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define N 100000+5
#define inf 0x3f3f3f3f
using namespace std;
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]

	int root;//根节点
	int fa[N];//父亲结点
	int ch[N][2];//孩子结点
	int sz[N];//以结点i为子树的结点数
	int top1;//曾经用过的结点
	int top2;//可用结点栈的栈顶
	int ss[N];//可用结点栈
	int que[N];//回收节点用到的队列
	int num[N];//结点的权值
	int val[N];//结点的值
	int minv[N];//区间最大值
	bool rev[N];
	int nodeNum;
    void rever(int x)
    {
        rev[x]^=1;
        swap(LC,RC);
    }
    void flip(int l,int r)
    {
        rotateto(l-1,0);
        rotateto(r+1,root);
        rever(KT);
    }
	void pushup(int x)
	{
		sz[x]=1+sz[LC]+sz[RC];//如果左子树为空,则LC=0,而sz[0]=0,即如果结点某个结点的子节点不存在,则指向空结点0,空节点的sz=0,不会造成错误
		minv[x]=min(minv[LC],minv[RC]);
		minv[x]=min(minv[x],val[x]);
	}
	void pushdown(int x)
	{
	    if(!rev[x]) return;
	    rever(LC);rever(RC);
	    rev[x]=0;
	}
	int getminv_id(int l,int r)
	{
        rotateto(l-1,0);
        rotateto(r+1,root);
        int tmp=minv[KT];
        int id=l-1;
        int x=KT;
        pushdown(x);
        while(val[x]!=tmp)
        {
            if(minv[LC]==tmp) x=LC;
            else
            {
                id+=sz[LC]+1;
                x=RC;
            }
            pushdown(x);
        }
        return id+sz[LC]+1;
    }

	void rotate(int x, bool f) //旋转
	{
		int y=fa[x];
		int z=fa[y];
		pushdown(y);
		pushdown(x);
		ch[y][!f]=ch[x][f];
		fa[ch[x][f]]=y;
		fa[x]=z;
		if(z)
		{
			ch[z][ch[z][1]==y]=x;
		}
		ch[x][f]=y;
		fa[y]=x;
		pushup(y);
	}
    void splay(int x, int g) //把结点x转到结点g下
	{
		int y=fa[x];
		pushdown(x);
        while (y!=g)
        {
			int z=fa[y];
			bool f=(ch[y][0]==x);
			if (z!=g && f==(ch[z][0]==y))
			{
				rotate(y,f);
			}
			rotate(x,f);
			y=fa[x];
		}
		pushup(x);
		if(g==0)
		{
			root=x;
		}
	}

	void rotateto(int k,int g) {	//把第k个结点转到结点g下,从第0个开始,因为有附加结点
		int x=root;
		pushdown(x);
		while (sz[LC]!=k)
		{
			if (k<sz[LC])
			{
				x=LC;
			} else
			{
				k-=(sz[LC]+1);
				x=RC;
			}
			pushdown(x);
		}
		splay(x,g);
	}

	void newNode(int &x,int c)
	{
		if (top2)
		{//ss栈是存储删掉的结点,这些结点可用,如果该栈不空,直接用这里面的结点号
			x=ss[--top2];
		}
		else
		{
			x=++top1;//如果没有可用结点,则增加结点数。
		}
		LC=RC=fa[x]=0;
		sz[x]=1;
		rev[x]=0;
		val[x]=c;
		minv[x]=c;
	}

	void makeTree(int &x,int l,int r,int f)
	{
		if (l>r)
		{
			return;
		}
		int m=(l+r)>>1;
		newNode(x,num[m]);	/*num[m]权值改成题目所需的*/
		makeTree(LC,l,m-1,x);
		makeTree(RC,m + 1,r,x);
		fa[x]=f;
		pushup(x);//建立树的时候,从下往上依次pushup
	}
	void init(int n)
	{
		nodeNum=n;
		ch[0][0]=ch[0][1]=fa[0]=sz[0]=0;//0结点是空节点,代表没有
		minv[0]=inf;
		rev[0]=0;
		root=top1=top2=0;
		//为了方便处理边界,加两个边界顶点
		newNode(root,inf);
		newNode(ch[root][1],inf);//这两个边界结点的值不影响正常求解
		fa[top1]=root;
		sz[root]=2;
		makeTree(KT,1,n,ch[root][1]);
		pushup(ch[root][1]);
		pushup(root);
	}
	void dfs(int x)
	{
	    if(x==0) return;
	    dfs(LC);
	    printf("%d ",val[x]);
	    dfs(RC);

	}
}spt;
typedef struct Node{
    int v,pos;
}Node;
Node node[N];
bool cmp(Node a,Node b)
{
    if(a.v!=b.v) return a.v<b.v;
    return a.pos<b.pos;
}
int main()
{
    int i,j;
    int n,m;
    while(~scanf("%d",&n) && n)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&node[i].v);
            node[i].pos=i;
        }
        sort(node+1,node+1+n,cmp);
        for(i=1;i<=n;i++) spt.num[node[i].pos]=i;
        spt.init(n);
        bool flag=1;
        for(i=1;i<=n;i++)
        {
            int ret=spt.getminv_id(i,n);
            spt.flip(i,ret);
            if(flag) flag=0;else printf(" ");
            printf("%d",ret);
        }
        printf("\n");
    }
    return 0;
}

HYSBZ 1588 营业额统计
一直wa,加了句if(scanf(“%lld”,&tmp)==EOF) tmp=0;就ac了,实在不太懂,求高手不吝解惑

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 50000+5
#define inf 100000000000000000LL
typedef long long ll;
inline ll min(ll a,ll b){return a<b?a:b;}
struct SplayTree {
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]

	int root;//根节点
	int fa[N];//父亲结点
	int ch[N][2];//孩子结点
	int top1;//曾经用过的结点
	int top2;//可用结点栈的栈顶
	int ss[N];//可用结点栈
	int que[N];//回收节点用到的队列
    ll val[N];

	void rotate(int x, bool f) //旋转
	{
		int y=fa[x];
		int z=fa[y];
		ch[y][!f]=ch[x][f];
		fa[ch[x][f]]=y;
		fa[x]=z;
		if(z)
		{
			ch[z][ch[z][1]==y]=x;
		}
		ch[x][f]=y;
		fa[y]=x;
	}

	void splay(int x, int g) //把结点x转到结点g下
	{
		int y=fa[x];
        while (y!=g)
        {
			int z=fa[y];
			bool f=(ch[y][0]==x);
			if (z!=g && f==(ch[z][0]==y))
			{
				rotate(y,f);
			}
			rotate(x,f);
			y=fa[x];
		}
		if(g==0)
		{
			root=x;
		}
	}

	void newNode(int &x,ll c)
	{
		if (top2)
		{//ss栈是存储删掉的结点,这些结点可用,如果该栈不空,直接用这里面的结点号
			x=ss[--top2];
		}
		else
		{
			x=++top1;//如果没有可用结点,则增加结点数。
		}
		LC=RC=fa[x]=0;
		val[x]=c;
	}
	void init()
	{
		ch[0][0]=ch[0][1]=fa[0]=0;//0结点是空节点,代表没有
		root=top1=top2=0;
		//为了方便处理边界,加两个边界顶点
		newNode(root,-inf);
		newNode(ch[root][1],inf);//这两个边界结点的值不影响正常求解
		fa[top1]=root;
	}
	int insert(int &x,ll v,int f)
	{
        if(!x)
        {
            newNode(x,v);fa[x]=f;return x;
        }
        if(val[x]==v) return 0;
        int ret;
        if(v<val[x]) ret=insert(LC,v,x);
        if(v>val[x]) ret=insert(RC,v,x);
        return ret;
    }
    ll findpre(int x)
    {
        splay(x,0);
        int key=x;
        x=LC;
        while(RC) x=RC;
        return val[key]-val[x];
    }
    ll findnext(int x)
    {
        splay(x,0);
        int key=x;
        x=RC;
        while(LC) x=LC;
        return val[x]-val[key];
    }

}spt;
int main()
{
    int i,j;
    int n;
    while(~scanf("%d",&n))
    {
        ll sum=0,tmp;
        spt.init();
        for(i=1;i<=n;i++)
        {
            if(scanf("%lld",&tmp)==EOF) tmp=0;
            int ret=spt.insert(spt.root,tmp,0);
            if(i==1) {sum+=tmp;continue;}
            if(ret==0) continue;
            ll tmp1=spt.findpre(ret),tmp2=spt.findnext(ret);
            sum+=min(tmp1,tmp2);
        }
        printf("%lld\n",sum);
    }
    return 0;
}

hdoj2475 Box
通过这道题我终于理解了splay森林的建法以及splay的“序”
思路:用一对括号表示一个盒子,开始时splay中没有点,然后按照盒子间的拓扑序插入括号。这样就保证splay中起始的序是正确的。为了splay等操作的方便,盒子的编号和节点编号保持一致。开始的时候,将盒子(x,x+n)剪下来的时候用的是findpre(),findnext()操作找到盒子x的前驱和后继,然后splay(前驱,0),splay(后继,前驱),然后减下x盒子,但是无情的TLE了,,然后改成splay(x,0),splay(x+n,x)。然后手工改变ch[x+n][1]和ch[x][0],将ch[x+n][1]作为根,将ch[x][0]插入ch[x+n][1]左边为空的左孩子,这样也能把x盒子裁剪下来,然后能ac了。。(ps:为毛前后两者效率相差那么大啊)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 100000+10
#define inf 0x3f3f3f3f
#define LC ch[x][0]
#define RC ch[x][1]
#define maxe 60000+10
#define maxn 60000+10
typedef struct Edge{
    int to,next;
}Edge;
Edge edge[maxe];
int head[maxn];
int cnt,n,m;
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;
    return;
}
int a[maxn];
int ind[maxn];
int q[maxn+10],iq;
struct SplayTree {
    int fa[N];//父亲结点
    int ch[N][2];//孩子结点
    int n;

    void rotate(int x, bool f) {    //旋转
        int y = fa[x];
        int z = fa[y];
        ch[y][!f] = ch[x][f];
        fa[ch[x][f]] = y;
        fa[x] = z;
        if (z) {
            ch[z][ch[z][1] == y] = x;
        }
        ch[x][f] = y;
        fa[y] = x;
    }

    void splay(int x, int g) {    //把结点x转到结点g下
        int y = fa[x];
/*
        while (y != g) {
            int z = fa[y];
            bool f = (ch[y][0] == x);
            if (z != g && f == (ch[z][0] == y)) {
                rotate(y, f);
            }
            rotate(x, f);
            y = fa[x];
        }
        */
        while (y != g) {
            rotate(x, ch[y][0] == x);
            y = fa[x];
        }

    }
    void init()
    {
        ch[0][0] = ch[0][1] = fa[0] = 0;//0结点是空节点,代表没有
    }
    void initnode(int x)
    {
        ch[x][0]=ch[x][1]=0;fa[x]=0;
    }
    int findpre(int x)
    {
        x=LC;
        while(RC) x=RC;
        return x;
    }
    int findnext(int x)
    {
        x=RC;
        while(LC) x=LC;
        return x;
    }
    void insert1(int x)
    {
        initnode(x);
        ch[x][1]=x+n;
        initnode(x+n);
        fa[x+n]=x;
    }
    void insert2(int x,int f)
    {
        splay(f,0);
        int next=findnext(f);
        splay(next,f);
        initnode(x);
        fa[x]=next;
        ch[next][0]=x;
        ch[x][1]=x+n;
        initnode(x+n);
        fa[x+n]=x;
        return;
    }
    bool judge(int x,int y)
    {
        if(x==y) return 0;
        splay(x,0);splay(x+n,x);
        while(y)
        {
            if(ch[x+n][0]==y) return 0;
            y=fa[y];
        }
        return 1;
    }
    void cutto(int x,int y)
    {
        int tmp;
        if(a[x]==0 && y==0) return;
        if(a[x])
        {
            fa[ch[x+n][1]]=0;
            int xh=ch[x+n][1];
            while(ch[xh][0]) xh=ch[xh][0];
            ch[xh][0]=ch[x][0];
            fa[ch[x][0]]=xh;
            ch[x+n][1]=0;
            ch[x][0]=0;
        }
        if(y!=0)
        {
            splay(y,0);
            tmp=findnext(y);
            splay(tmp,y);
            fa[x]=tmp;
            ch[tmp][0]=x;
        }
        a[x]=y;
        return;
    }
    int query_rootbox(int x)
    {
        splay(x,0);
        while(LC) x=LC;
        return x;
    }
    void dfs(int x)
    {
        if(x==0) return;
        dfs(LC);
        printf("%d ",x);
        dfs(RC);
    }
}spt;
void topsort()
{
    iq=0;
    int i,j;
    for(i=1;i<=n;i++)
        if(ind[i]==0) q[iq++]=i;
    for(i=0;i<=iq-1;i++)
    {
        int u=q[i];
        for(j=head[u];j!=-1;j=edge[j].next)
        {
            int v=edge[j].to;
            ind[v]--;
            if(!ind[v]) q[iq++]=v;
        }
    }
    return;
}
void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    int i,j;
    int x,y;
    bool flag=1;
    while(~scanf("%d",&n))
    {
        spt.n=n;
        cnt=0;memset(head,-1,sizeof(int)*(n+5));
        memset(ind,0,sizeof(int)*(n+5));
        for(i=1;i<=n;i++)
        {
            scan(a[i]);
            if(a[i]==0) continue;
            add(a[i],i);
            ind[i]++;
        }
        topsort();
        spt.init();
        for(i=0;i<=iq-1;i++)
        {
            if(a[q[i]]==0) spt.insert1(q[i]);
            else spt.insert2(q[i],a[q[i]]);
        }
/*
        for(i=1;i<=n;i++)
            if(a[i]==0) {spt.splay(i,0);spt.dfs(i);printf("\n");}
*/
        scanf("%d",&m);
        char com[10];
        if(!flag) printf("\n");else flag=0;
        while(m--)
        {
            scanf("%s",com);
            if(com[0]=='M')
            {
                scan(x);scan(y);
                if(!spt.judge(x,y)) continue;
                if(a[x]==y) continue;
                spt.cutto(x,y);
/*
            for(i=1;i<=n;i++)
                if(a[i]==0) {spt.splay(i,0);spt.dfs(i);printf("\n");}
*/
                continue;
            }
            scan(x);
            printf("%d\n",spt.query_rootbox(x));
        }
    }
    return 0;
}

bzoj 1208 宠物收养所
简单题,但是不知道为什么long long会TLE,int就A了。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
#define N 100000+10
#define inf 0x3f3f3f3f
#define mod 1000000
struct SplayTree {
    int root;//根节点
	int fa[N];//父亲结点
	int ch[N][2];//孩子结点
	int sz[N];//以结点i为子树的结点数
	int val[N];//结点的值
	int nodenum;
	int num;
	void pushup(int x)
	{
        sz[x]=sz[LC]+sz[RC]+1;
        return;
	}
    void rotate(int x, bool f) {	//旋转
		int y = fa[x];
		int z = fa[y];
		ch[y][!f] = ch[x][f];
		fa[ch[x][f]] = y;
		fa[x] = z;
		if (z) {
			ch[z][ch[z][1] == y] = x;
		}
		ch[x][f] = y;
		fa[y] = x;
		pushup(y);
	}

	void splay(int x, int g) {	//把结点x转到结点g下
		int y = fa[x];
		while (y != g) {
			int z = fa[y];
			bool f = (ch[y][0] == x);
			if (z != g && f == (ch[z][0] == y)) {
				rotate(y, f);
			}
			rotate(x, f);
			y = fa[x];
		}
		pushup(x);
		if (g == 0) {
			root = x;
		}
	}

	void rotateto(int k, int g)
	{	//把第k个结点转到结点g下
		int x = root;
		while (sz[LC]!=k) {
			if (k<sz[LC]) {
				x=LC;
			} else {
				k-=sz[LC]+1;
				x=RC;
			}
		}
		splay(x,g);
		return;
	}
    void init() {
		root=nodenum=num=0;
		ch[0][0]=ch[0][1]=fa[0]=sz[0]=0;
		ch[1][0]=ch[1][1]=0;fa[1]=0;sz[1]=2;ch[1][1]=2;val[1]=-inf;
		ch[2][0]=ch[2][1]=0;fa[2]=1;sz[2]=1;val[2]=inf;
		root=1;
		num=2;
		return;
	}
	void insert(int &x,int v,int f)
	{
        if(!x)
        {
            x=++num;
            val[x]=v;
            sz[x]=1;
            ch[x][0]=ch[x][1]=0;fa[x]=f;
            nodenum++;
            return;
        }
        if(v<val[x]) insert(LC,v,x);
        else insert(RC,v,x);
        pushup(x);
        return;
	}
	int findpre(int x)
	{
        x=LC;
        while(RC) x=RC;
        return x;
	}
	int findnext(int x)
	{
        x=RC;
        while(LC) x=LC;
        return x;
	}
	int rank(int v)
	{
	    int x=root,cnt=0;
	    while(x)
        {
            if(val[x]==v) {cnt+=sz[LC];break;}
            else if(v<val[x])
            {
                x=LC;
            }
            else
            {
                cnt+=sz[LC]+1;
                x=RC;
            }
        }
        return cnt;
	}
	void erase(int x)
	{
	    nodenum--;
	    int tmp=rank(val[x]);
	    rotateto(tmp-1,0);
	    rotateto(tmp+1,root);
	    KT=0;
	    pushup(ch[root][1]);
	    pushup(root);
	    return;
    }
	int query(int b)
	{
        int tmp=rank(b);
        rotateto(tmp,0);
        int pre=findpre(root);
        int v1=val[pre],v2=val[root];
        if(abs(v1-b)<=abs(v2-b))
        {
            erase(pre);
            return abs(v1-b);
        }
        erase(root);
        return abs(v2-b);
	}
}spt;
void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    int i,j;
    int n,a,b;
    while(~scanf("%d",&n))
    {
        int sum=0;
        int type;
        spt.init();
        while(n--)
        {
            scan(a);scan(b);
            if(spt.nodenum==0)
            {
                type=a;
                spt.insert(spt.root,b,0);
                continue;
            }
            if(a==type)
            {
                spt.insert(spt.root,b,0);
                continue;
            }
            sum=(sum+spt.query(b))%mod;
        }
        printf("%d\n",sum);
    }
    return 0;
}

bzoj1507 Editor
这题实在是坑,首先样例中的第一个Delete操作是非法的(题意说不会非法),而且不是故意非法而是10写成了11.。
其次insert时的字符串长度没告诉,RE几次,当然严格来说这个是自己做题疏忽,题意说总共insert的字符数是2M。所以一次最多插入2M的字符,数组应当开到2*10^6左右。。。

#include<stdio.h>
#include<string.h>
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
#define inf 0x3f3f3f3f
#define N 2000000+10
struct SplayTree {
    int root;//根节点
	int fa[N];//父亲结点
	int ch[N][2];//孩子结点
	int sz[N];//以结点i为子树的结点数
	char val[N];//结点的值
	int num;
    int cur;
    void pushup(int x)
    {
        sz[x]=sz[LC]+sz[RC]+1;
        return;
    }
	void rotate(int x, bool f) {	//旋转
		int y = fa[x];
		int z = fa[y];
		ch[y][!f] = ch[x][f];
		fa[ch[x][f]] = y;
		fa[x] = z;
		if (z) {
			ch[z][ch[z][1] == y] = x;
		}
		ch[x][f] = y;
		fa[y] = x;
		pushup(y);
	}

	void splay(int x, int g) {	//把结点x转到结点g下
		int y = fa[x];
		while (y != g) {
			int z = fa[y];
			bool f = (ch[y][0] == x);
			if (z != g && f == (ch[z][0] == y)) {
				rotate(y, f);
			}
			rotate(x, f);
			y = fa[x];
		}
		pushup(x);
		if (g == 0) {
			root = x;
		}
	}

	void rotateto(int k, int g) {	//把第k个结点转到结点g下
		int x = root;
		while (sz[LC]!=k) {
			if (k<sz[LC]) {
				x = LC;
			} else {
				k-=sz[LC]+1;
				x=RC;
			}
		}
		splay(x,g);
		return;
	}
	void newnode(int &x,char c)
	{
        x=++num;
        ch[x][0]=ch[x][1]=fa[x]=0;
        sz[x]=1;
        val[x]=c;
        return;
	}
	void init() {
		cur=num=0;
		ch[0][0] = ch[0][1] = fa[0] = sz[0] = 0;
		ch[1][0]=ch[1][1]=fa[1]=val[1]=0;
		ch[2][0]=ch[2][1]=fa[2]=val[2]=0;
		ch[1][1]=2;fa[2]=1;
		sz[1]=2;sz[2]=1;
		num=2;
		root=1;
		return;
    }
    void make(int &x,int l,int r,char s[],int f)
    {
        if(l>r) return;
        int mid=(l+r)/2;
        newnode(x,s[mid]);
        make(LC,l,mid-1,s,x);
        make(RC,mid+1,r,s,x);
        fa[x]=f;
        pushup(x);
        return;
    }
    void insert(int n,char s[])
    {
        rotateto(cur,0);
        rotateto(cur+1,root);
        make(KT,1,n,s,ch[root][1]);
        pushup(ch[root][1]);
        pushup(root);
        return;
    }
    void del(int n)
    {
        rotateto(cur,0);
        rotateto(cur+n+1,root);
        KT=0;
        pushup(ch[root][1]);
        pushup(root);
        return;
    }
    void get(int n)
    {
        rotateto(cur,0);
        rotateto(cur+n+1,root);
        mid_dfs(KT);
        printf("\n");
        return;
    }
    void mid_dfs(int x)
    {
        if(!x) return;
        mid_dfs(LC);
        printf("%c",val[x]);
        mid_dfs(RC);
    }
}spt;
void get_line(char *s,int n)
{
    char c;
    for(int i=1;i<=n;i++)
    {
        c=getchar();
        if(c=='\n') {i--;continue;}
        s[i]=c;
    }
    return;
}
char s[2000000];
int main()
{
    //freopen("F:\\test.in","r",stdin);
    int i,j,k;
    int t,n;
    char com[20];

    scanf("%d",&t);
    spt.init();
    while(t--)
    {
        scanf("%s",com);
        if(!strcmp(com,"Move"))
        {
            scanf("%d",&k);
            spt.cur=k;
            continue;
        }
        if(!strcmp(com,"Insert"))
        {
            scanf("%d",&n);
            get_line(s,n);
            spt.insert(n,s);
            continue;

        }
        if(!strcmp(com,"Delete"))
        {
            scanf("%d",&n);
            spt.del(n);
            continue;
        }
        if(!strcmp(com,"Get"))
        {
            scanf("%d",&n);
            spt.get(n);
            continue;
        }
        if(!strcmp(com,"Prev")) {spt.cur--;continue;}
        if(!strcmp(com,"Next")) {spt.cur++;continue;}
    }
    return 0;
}

bzoj1269 文本编辑器editor
上一题的加强版,加入了旋转操作,这样就需要延迟标记啦。get操作变成输出一个字符。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define KT ch[ch[root][1]][0]
#define LC ch[x][0]
#define RC ch[x][1]
#define inf 0x3f3f3f3f
#define N 3000000+10
using namespace std;
struct SplayTree {
    int root;//根节点
	int fa[N];//父亲结点
	int ch[N][2];//孩子结点
	int sz[N];//以结点i为子树的结点数
	char val[N];//结点的值
	int rev[N];
	int num;
    int cur;
    void pushup(int x)
    {
        sz[x]=sz[LC]+sz[RC]+1;
        return;
    }
    void rever(int x)
    {
        swap(LC,RC);
        rev[x]^=1;
        return;
    }
    void flip(int l,int r)
    {
        rotateto(l-1,0);
        rotateto(r+1,root);
        rever(KT);
        return;
    }
    void pushdown(int x)
    {
        if(!rev[x]) return;
        rever(LC);
        rever(RC);
        rev[x]=0;
        return;
    }
	void rotate(int x, bool f) {	//旋转
		int y = fa[x];
		int z = fa[y];
		pushdown(y);
		pushdown(x);
		ch[y][!f] = ch[x][f];
		fa[ch[x][f]] = y;
		fa[x] = z;
		if (z) {
			ch[z][ch[z][1] == y] = x;
		}
		ch[x][f] = y;
		fa[y] = x;
		pushup(y);
	}

	void splay(int x, int g) {	//把结点x转到结点g下
		int y = fa[x];
		pushdown(x);
		while (y != g) {
			int z = fa[y];
			bool f = (ch[y][0] == x);
			if (z != g && f == (ch[z][0] == y)) {
				rotate(y, f);
			}
			rotate(x, f);
			y = fa[x];
		}
		pushup(x);
		if (g == 0) {
			root = x;
		}
	}

	void rotateto(int k, int g) {	//把第k个结点转到结点g下
		int x = root;
		pushdown(x);
		while (sz[LC]!=k) {
			if (k<sz[LC]) {
				x = LC;
			} else {
				k-=sz[LC]+1;
				x=RC;
			}
			pushdown(x);
		}
		splay(x,g);
		return;
	}
	void newnode(int &x,char c)
	{
        x=++num;
        ch[x][0]=ch[x][1]=fa[x]=0;
        sz[x]=1;
        val[x]=c;
        rev[x]=0;
        return;
	}
	void init() {
		cur=num=0;
		ch[0][0] = ch[0][1] = fa[0] = sz[0]=rev[0] = 0;
		ch[1][0]=ch[1][1]=fa[1]=val[1]=rev[1]=0;
		ch[2][0]=ch[2][1]=fa[2]=val[2]=rev[2]=0;
		ch[1][1]=2;fa[2]=1;
		sz[1]=2;sz[2]=1;
		num=2;
		root=1;
		return;
    }
    void make(int &x,int l,int r,char s[],int f)
    {
        if(l>r) return;
        int mid=(l+r)/2;
        newnode(x,s[mid]);
        make(LC,l,mid-1,s,x);
        make(RC,mid+1,r,s,x);
        fa[x]=f;
        pushup(x);
        return;
    }
    void insert(int n,char s[])
    {
        rotateto(cur,0);
        rotateto(cur+1,root);
        make(KT,1,n,s,ch[root][1]);
        pushup(ch[root][1]);
        pushup(root);
        return;
    }
    void del(int n)
    {
        rotateto(cur,0);
        rotateto(cur+n+1,root);
        KT=0;
        pushup(ch[root][1]);
        pushup(root);
        return;
    }
    void get()
    {
        rotateto(cur+1,0);
        printf("%c\n",val[root]);
        return;
    }
    void mid_dfs(int x)
    {
        if(!x) return;
        mid_dfs(LC);
        printf("%c",val[x]);
        mid_dfs(RC);
    }
}spt;
void get_line(char *s,int n)
{
    char c;
    for(int i=1;i<=n;i++)
    {
        c=getchar();
        if(c=='\n') {i--;continue;}
        s[i]=c;
    }
    return;
}
char s[3000000];
int main()
{
    //freopen("F:\\test.in","r",stdin);
    int i,j,k;
    int t,n;
    char com[20];

    scanf("%d",&t);
    spt.init();
    while(t--)
    {
        scanf("%s",com);
        if(!strcmp(com,"Move"))
        {
            scanf("%d",&k);
            spt.cur=k;
            continue;
        }
        if(!strcmp(com,"Insert"))
        {
            scanf("%d",&n);
            get_line(s,n);
            spt.insert(n,s);
            continue;

        }
        if(!strcmp(com,"Delete"))
        {
            scanf("%d",&n);
            spt.del(n);
            continue;
        }
        if(!strcmp(com,"Get"))
        {
            spt.get();
            continue;
        }
        if(!strcmp(com,"Rotate"))
        {
            scanf("%d",&n);
            spt.flip(spt.cur+1,spt.cur+n);
            continue;
        }
        if(!strcmp(com,"Prev")) {spt.cur--;continue;}
        if(!strcmp(com,"Next")) {spt.cur++;continue;}
    }
    return 0;
}

线段树优化dp,待做

poj3171
lightoj 1415
bzoj1835
uestc 1501
poj2376
poj2374
zjoi2010
fafu1231 http://acm.fafu.edu.cn/problem.php?id=1231
poj2355
hdoj4719
uestc1558
接下来要深入学习不单调的斜率优化dp,线段树深入,线性规划,分数规划,还有splay和可持久化的一些数据结构

hdoj3698 Let the light guide us——线段树优化dp

终于ac了,好久不写线段树,成段更新变生疏了。
第一道用线段树优化的dp题。线段树用于成段更新,求区间最小值(包括历史值在内的最小值)。
dp[i][j]:前i行,且第i行选第j个可以得到的最小花费
dp[i][j]=min{dp[i-1][k]|1<=k<=m且abs(j-k)<=f[i-1][k]+f[i][j]}+cost[i][j]
复杂度n*m*m,超时
其实对于确定的i,j可以选择哪些k呢?abs(j-k)<=f[i][j]+f[i-1][k]等价于以j为中心,f[i][j]为半径的区间和以k为中心,f[i-1][k]为半径的区间的重合部分,so。。求解每个阶段的时候,可以建立线段树[1,m],然后不断加入上个阶段的dp值,dp[i-1][k]的区间是
[max(1,k-f[i-1][k]),min(m,k+f[i-1][k])],线段树维护最小值,注意lazy字段,lazy表示要往下更新的最小值,但是子孙节点的lazy有可能是小于它的(加入先对父区间更新为10,然后左子区间更新为8,这时候子区间的lazy就要比父区间小了),所以pushdown的时候,只有儿子节点的lazy没值或者小于父节点的lazy,才能重写这个儿子节点的lazy,否则可能导致结果偏大

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define lson id<<1
#define rson id<<1|1
#define maxn 110
#define maxm 5020
#define inf (0x3f3f3f3f)*2
int cost[maxn][maxm],f[maxn][maxm],dp[maxn][maxm];
int x[4*maxm];
int lazy[4*maxm];
int n,m;
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
void pushup(int id)
{
    x[id]=min(x[lson],x[rson]);
    return;
}
void pushdown(int id)
{
    if(lazy[id]==-1) return;
    if(lazy[lson]==-1 || lazy[id]<lazy[lson])
    {
        lazy[lson]=lazy[id];
    }
    if(lazy[rson]==-1 || lazy[id]<lazy[rson])
    {
        lazy[rson]=lazy[id];
    }
    x[lson]=min(x[lson],lazy[id]);
    x[rson]=min(x[rson],lazy[id]);
    lazy[id]=-1;
    return;
}
void update(int id,int l,int r,int L,int R,int v)
{
    if(L<=l && r<=R)
    {
        x[id]=min(x[id],v);
        if(lazy[id]==-1 || v<lazy[id]) lazy[id]=v;
        return;
    }
    pushdown(id);
    int mid=l+(r-l)/2;
    if(L<=mid) update(lson,l,mid,L,R,v);
    if(R>mid) update(rson,mid+1,r,L,R,v);
    pushup(id);
    return;
}
int query(int id,int l,int r,int L,int R)
{
    if(L<=l && r<=R) return x[id];
    pushdown(id);
    int mid=l+(r-l)/2,ret=inf;
    if(L<=mid) ret=min(ret,query(lson,l,mid,L,R));
    if(R>=mid+1) ret=min(ret,query(rson,mid+1,r,L,R));
    return ret;
}
int solve()
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        memset(x,inf,sizeof(int)*(4*m+10));
        memset(lazy,-1,sizeof(int)*(4*m+10));
        for(j=1;j<=m;j++)
            update(1,1,m,max(1,j-f[i-1][j]),min(m,j+f[i-1][j]),dp[i-1][j]);
        for(j=1;j<=m;j++)
            dp[i][j]=cost[i][j]+query(1,1,m,max(1,j-f[i][j]),min(m,j+f[i][j]));
    }
    int ret=inf;
    for(i=1;i<=m;i++) ret=min(ret,dp[n][i]);
    return ret;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&cost[i][j]);
                dp[i][j]=(i==1?cost[i][j]:inf);
            }
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&f[i][j]);
        printf("%d\n",solve());
    }
    return 0;
}