4
17
2016
0

C++模板学习

之前因为什么奇怪的原因抱回来一本C++ Primer,认真研读之后发现什么都没看懂

但是唯一明白的就是我之前一直不会写C++啊。

然后大致草草的明白了类和继承和OOP编程的基础开始学习模板

写了各线段树的模板…… 区间修改的借口还待调试

#ifndef SEGMENT_TREE
#define SEGMENT_TREE

//这是一个我想使用的标准线段书模板
//我们需要提供节点类型,每个节点类型都必须包含push_down,push_up,两种操作
//如果使用函数的modify string 命令接口那么必须包含modify(std::string &)接口
//如果不想要使用这个接口,可以使用#define NOSTRINGMODIFY 来避免这个借口带来的编译问题
//其中modify可以接受一个字符串作为目的的操作
//这里我们提供一种标准的 class StandardNode 可以从中继承使用
#include <string>
#include <cmath>
const int DEFUALTSEGMENTSIZE = 100000;
template <typename T>
class SegmentTree{
public:
	explicit SegmentTree(int Size);
	explicit SegmentTree(T *,int Size);
	~SegmentTree();
	void init(T *);
	void modify(int pos,const T &x);
#ifndef NOSTRINGMODIFY
	void modify(int l,int r,const std::string &cmd);
	void modify(int l,int r,const std::string &cmd,const T &x);
#endif
	T query(int l,int r);
private:
	int Size;
	void build(int i,int l,int r,T *);
	void build(int i,int l,int r);
	void modify(int i,int pos,const T &x);
#ifndef UNFINSHIED
	void modify(int i,int l,int r,const std::string &cmd);
	void modify(int i,int l,int r,const std::string &cmd,const T &x);
	inline void push_up(int i);
	inline void push_down(int i);
#endif
	T query(int i,int l,int r);
	int D;
	class segmentTreeNodeClass{
	public:
		T data;
		int l,r;
		int mid(){ return l+r>>1; }
	}*s;
};

template<typename T>
SegmentTree<T>::SegmentTree(int _Size):Size(_Size){
	D = (int)ceil(log(Size) / log(2)); 
	s = new segmentTreeNodeClass[1 << D+1];
	build(1,1,1 << D);
}

template<typename T>
SegmentTree<T>::SegmentTree(T *x,int Size):Size(Size){
	D = (int)ceil(log(Size) / log(2)); 
	s = new segmentTreeNodeClass[1 << D+1];
	build(1,1,1 << D,x);
}

template<typename T>
SegmentTree<T>::~SegmentTree(){
//currently do nothing at all
}	

template<typename T>
void SegmentTree<T>::init(T *x){
	build(1,1,1<<D,x);
}

template<typename T>
void SegmentTree<T>::modify(int pos,const T &x){
	modify(1,pos,x);
}
#ifndef NOSTRINGMODIFY
template<typename T>
void SegmentTree<T>::modify(int l,int r,const std::string &cmd){
	modify(1,l,r,cmd);
}

template<typename T>
void SegmentTree<T>::modify(int l,int r,const std::string &cmd,const T &x){
	modify(1,l,r,cmd,x);
}
#endif

template<typename T>
T SegmentTree<T>::query(int l,int r){
	return query(1,l,r);
}

template<typename T>
void SegmentTree<T>::build(int i,int l,int r){
	s[i].l = l;
	s[i].r = r;
	s[i].data.setRange(l,r);
	if (l==r) return;
	int m = l+r>>1;
	build(i<<1,l,m);
	build(i<<1|1,m+1,r);
}

template<typename T>
void SegmentTree<T>::build(int i,int l,int r,T *x){
	s[i].l = l;
	s[i].r = r;
	s[i].data.setRange(l,r);
	if (l==r){
		if (l <= Size) s[i].data = x[l];
		s[i].data.setRange(l,r);
		return;
	}
	int m = l+r>>1;
	build(i<<1,l,m,x);
	build(i<<1|1,m+1,r,x);
	push_up(i);
	return;
}

template<typename T>
void SegmentTree<T>::modify(int i,int pos,const T &x){
	if (s[i].l==pos && s[i].r==pos){
		s[i].data = x;
		s[i].data.setRange(pos,pos);
		return;
	}
	push_down(i);
	if (pos <= s[i].mid()) modify(i<<1,pos,x);
	else modify(i<<1|1,pos,x);
	push_up(i);
}

#ifndef NOSTRINGMODIFY
template<typename T>
void SegmentTree<T>::modify(int i,int l,int r,const std::string &cmd){
	if (s[i].l==l && s[i].r==r){
		s[i].data.modify(cmd);
		return;
	}
	push_down(i);
	int m = s[i].mid();
	if (r<=m) modify(i<<1,l,r,cmd);
	else if (l>m) modify(i<<1|1,l,r,cmd);
	else modify(i<<1,l,m,cmd),modify(i<<1,m+1,r,cmd);
	push_up(i);
}


template<typename T>
void SegmentTree<T>::modify(int i,int l,int r,const std::string &cmd,const T &x){
	if (s[i].l==l && s[i].r==r){
		s[i].data.modify(cmd,x);
		return;
	}
	push_down(i);
	int m = s[i].mid();
	if (r<=m) modify(i<<1,l,r,cmd,x);
	else if (l>m) modify(i<<1|1,l,r,cmd,x);
	else modify(i<<1,l,m,cmd,x),modify(i<<1,m+1,r,cmd,x);
	push_up(i);
}
#endif

template<typename T>
T SegmentTree<T>::query(int i,int l,int r){
	if (s[i].l==l && s[i].r==r) return s[i].data;
	int m=s[i].mid();
	T ret;
	push_down(i);
	if (r<=m) ret = query(i<<1,l,r);
	else if (l>m) ret =query(i<<1|1,l,r);
	else ret.push_up(query(i<<1,l,m),query(i<<1|1,m+1,r));
	push_up(i);
	return ret;
}

template<typename T>
inline void SegmentTree<T>::push_up(int i){
	s[i].data.push_up(s[i<<1].data,s[i<<1|1].data);
}

template<typename T>
inline void SegmentTree<T>::push_down(int i){
	s[i].data.push_down(s[i<<1].data,s[i<<1|1].data);
}

class StandardNode{
public:
	virtual void push_up(const StandardNode &x,const StandardNode &y)  {}
	virtual void push_down(StandardNode &x,StandardNode &y)  {}
	virtual void modify(const std::string &cmd)  {}
	virtual void modify(const std::string &cmd,const StandardNode &x)  {}
	virtual void setRange(int l,int r){}	
	virtual ~StandardNode(){}
};
#endif
Category: 未分类 | Tags: C++ 模板 线段树
6
11
2015
2

bzoj 4127: Abs

这就是线段树解决区间覆盖的一类毒瘤问题

自从xyz111在cf上出了那道线段树解决区间覆盖问题之后,这已经几乎成为了一种毒瘤算法,这道题可以说是有过之而无不及。首先我们考虑一个区间内有正有负,加完之后绝对值的和和三部分有关系1.有负数变成负数,2.由正数变成正数,3.有负数变成正数,前面两种非常好讨论,只有第三种有苦难。但是我们注意到第三种每个数字只会出现一次,所以就变成了区间覆盖的那一类问题,用区间覆盖线段树来解决,复杂度通过势能分析。

所以树链剖分之后随便搞一搞复杂度 $$ O(nlog^2n) $$

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <iostream>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
#define LL long long
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch>'9' || ch<'0';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 100010;
int son[N],fa[N],d[N],p[N][20],q[N],w[N],v[N],a[N],top[N],vis[N];
int start[N],to[N<<1],next[N<<1],size[N],cnt;
inline void connect(int a,int b){
	to[++cnt]=b; next[cnt]=start[a]; start[a]=cnt;
}
int n,m;
struct node{
	int l,r;
	int vmax,num;
	LL sum,flag;
	inline int mid(){ return r+l>>1; }
	inline int len(){ return r-l+1; }
	inline void add(LL x){
		if (vmax!=0 && vmax+x>=0) printf("Wrong!!!\n");
		if (vmax!=0) vmax+=x;
		flag+=x;
		sum+=x*(len()-num-num);
	} 
}s[N<<2];
void init(){
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read(); m=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<n;i++){
		int x=read(),y=read();
		connect(x,y);
		connect(y,x);
	}
	int head=0,tail=1,u;
	q[1]=1; d[1]=1; fa[1]=0;
	while (head<tail){
		u=q[++head];
		for (int p=start[u];p;p=next[p]){
			int &v=to[p];
			if (d[v]) continue;
			d[v]=d[u]+1; fa[v]=u;
			q[++tail]=v;
		}
	}
	for (int i=n;i;i--){
		int x=q[i];
		size[x]++;
		size[fa[x]]+=size[x];
		if (size[son[fa[x]]]<size[x]) son[fa[x]]=x;
	}
	int now=0;			
	for (int i=1;i<=n;i++){
		int x=q[i];
		if (vis[x]) continue;
		for (int j=x;j;j=son[j]){
			top[j]=x;
			w[j]=++now;
			vis[j]=1;
			v[now]=a[j];
		}
	}
	for (int i=1;i<=n;i++) p[i][0]=fa[i];
	for (int j=1;j<20;j++)
		for (int i=1;i<=n;i++)
			p[i][j]=p[p[i][j-1]][j-1];
}
inline int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	int j;
	while (d[x]>d[y]){
		for (j=1;d[p[x][j]]>=d[y];j++);
		x=p[x][j-1];
	}
	while (x!=y){
		for (j=1;p[x][j]!=p[y][j];j++);
		x=p[x][j-1],y=p[y][j-1];
	}
	return x;	
}
inline void push_down(int x){
	if (s[x].r>s[x].l && s[x].flag){
		s[x<<1].add(s[x].flag);
		s[x<<1|1].add(s[x].flag);
		s[x].flag=0;
	}
}
inline int gvmax(int x,int y){
	if (x>=0) return y;
	if (y>=0) return x;
	return x>y?x:y;
}
inline void push_up(int x){
	s[x].sum=s[x<<1].sum+s[x<<1|1].sum;
	s[x].num=s[x<<1].num+s[x<<1|1].num;
	s[x].vmax=gvmax(s[x<<1].vmax,s[x<<1|1].vmax);
}
inline void build(int i,int l,int r){
	s[i].l=l; s[i].r=r;
	s[i].flag=0;
	if (l==r){
		s[i].num=v[l]<0?1:0;
		s[i].vmax=min(0,v[l]);
		s[i].sum=abs(v[l]);
		return;
	}
	int m=l+r>>1;
	build(i<<1,l,m); build(i<<1|1,m+1,r);
	push_up(i);
}
inline LL query(int i,int l,int r){
	if (s[i].l==l && s[i].r==r){
		return s[i].sum;
	}
	push_down(i);
	int m=s[i].mid();
	LL ret;
	if (r<=m) ret=query(i<<1,l,r);
	else if (l>m) ret=query(i<<1|1,l,r);
	else ret=query(i<<1,l,m)+query(i<<1|1,m+1,r);
	push_up(i);
	return ret;
}
inline void dfs(int i,int d){
	if (s[i].vmax==0 || s[i].vmax+d<0){
		s[i].add(d);
		return;
	}
	if (s[i].l==s[i].r){
		s[i].sum=s[i].vmax+d;
		s[i].vmax=0;
		s[i].num=0;
		return;
	}
	push_down(i);
	dfs(i<<1,d); 
	dfs(i<<1|1,d);
	push_up(i);
}
inline void modify(int i,int l,int r,int d){
	if (s[i].l==l && s[i].r==r){
		dfs(i,d);
		return;
	}
	push_down(i);
	int m=s[i].mid();
	if (r<=m) modify(i<<1,l,r,d);
	else if (l>m) modify(i<<1|1,l,r,d);
	else modify(i<<1,l,m,d),modify(i<<1|1,m+1,r,d);
	push_up(i);
}
inline LL Query(int x,int y){
	LL ans=0;
	int u=lca(x,y);
	while (d[x]>d[u]){
		if (d[top[x]]>d[u]){
			ans+=query(1,w[top[x]],w[x]);
			x=fa[top[x]];
		}else{
			ans+=query(1,w[son[u]],w[x]);
			x=u;
		}
	}
	swap(x,y);
	while (d[x]>d[u]){
		if (d[top[x]]>d[u]){
			ans+=query(1,w[top[x]],w[x]);
			x=fa[top[x]];
		}else{
			ans+=query(1,w[son[u]],w[x]);
			x=u;
		}
	}
	ans+=query(1,w[u],w[u]);
	return ans;
}
inline void Modify(int x,int y,int D){
	int u=lca(x,y);
	while (d[x]>d[u]){
		if (d[top[x]]>d[u]){
			modify(1,w[top[x]],w[x],D);
			x=fa[top[x]];
		}else{
			modify(1,w[son[u]],w[x],D);
			x=u;
		}
	}
	swap(x,y);
	while (d[x]>d[u]){
		if (d[top[x]]>d[u]){
			modify(1,w[top[x]],w[x],D);
			x=fa[top[x]];
		}else{
			modify(1,w[son[u]],w[x],D);
			x=u;
		}
	}
	modify(1,w[u],w[u],D);
	return;
}
void work()
{
	build(1,1,n);
	for (int i=1;i<=m;i++){
		int op=read(),x=read(),y=read();
		if (op==2){
			printf("%lld\n",Query(x,y));
		}else{
			int d=read();
			Modify(x,y,d);
		}
	}
}
int main()
{
	init();
	work();
	return 0;
}

 

 

Category: 未分类 | Tags: bzoj 线段树 区间覆盖

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com