HDU5956 The Elder 下凸壳的维护
面向对象的计算几何模板

HDU 5957 环套树+线段树维护bfs序

zjhl2 posted @ 2017年9月20日 21:58 in with tags 线段树 动态规划 , 919 阅读

题意:

n个点n条边的连通图,边长度都为1,没有重边自环,两种操作:

1.把与x距离小于等于k的所有点的权值增加d  (k<=2)

2.问离x距离小于等于k的所有点的权值和 (k<=2)

 

思路:

首先这是个环套树,找到环后从环上的每个点开始bfs,处理出每个点向子树走k步的bfs序区间,一层层维护就好了。

分类讨论比较麻烦。

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll lazy[4*N],sum[4*N];
int n;
void init()
{
    memset(lazy,0,sizeof(lazy));
    memset(sum,0,sizeof(sum));
}
void up(int x)
{
	sum[x]=sum[x*2]+sum[x*2+1];
}
void down(int x,int l,int r)
{
	if (lazy[x])
	{
		int mid=(l+r)/2;
		sum[x*2]+=(mid-l+1)*lazy[x];
		sum[x*2+1]+=(r-mid)*lazy[x];
		lazy[x*2]+=lazy[x];
		lazy[x*2+1]+=lazy[x];
		lazy[x]=0;
	}
}
void add(int i,int l,int r,int x,int y,int w)
{
	if (x<=l&&r<=y)
	{
		sum[i]+=w*(r-l+1);
		lazy[i]+=w;
		return;
	}
	down(i,l,r);
	int mid=(l+r)/2;
	if (x<=mid) add(i*2,l,mid,x,y,w);
	if (y>mid) add(i*2+1,mid+1,r,x,y,w);
	up(i);
}
ll get(int i,int l,int r,int x,int y)
{
	if (x<=l&&r<=y) return sum[i];
	down(i,l,r);
	int mid=(l+r)/2;
	ll ret=0;
	if (x<=mid) ret+=get(i*2,l,mid,x,y);
	if (y>mid) ret+=get(i*2+1,mid+1,r,x,y);
	return ret;
}

void ad(int l,int r,int w)
{
	if (l>r) return;
	add(1,1,n,l,r,w);
}
ll gt(int l,int r)
{
	if (l>r) return 0;
	return get(1,1,n,l,r);
}

bool vis[N],on[N];
int l[N],r[N];
vector<int>link[N];
int dfs1(int u,int fa)
{
	vis[u]=1;
	for (int i=0;i<link[u].size();i++)
	{
		int v=link[u][i];
		if (v==fa) continue;
		l[v]=u;
		if (vis[v]) return v;
		int tmp=dfs1(v,u);
		if (tmp) return tmp;
	}
	return 0;
}
int tot;
int q[N],bl[N][3],br[N][3],fa[N];
void bfs(int u)
{
	vis[u]=1;
	q[++tot]=u;
	bl[u][0]=tot; bl[u][1]=bl[u][2]=N;
	br[u][0]=tot; br[u][1]=br[u][2]=0;
	int head=tot;
	while(head<=tot)
	{
		int u=q[head]; head++;
		for (int i=0;i<link[u].size();i++)
		{
			int v=link[u][i];
			if (vis[v]||on[v]) continue;
			q[++tot]=v;
			bl[v][0]=tot; bl[v][1]=bl[v][2]=N;
			br[v][0]=tot; br[v][1]=br[v][2]=0;
			fa[v]=u;
			vis[v]=1;
		}
	}
}

void look(int n)
{
	for (int i=1;i<=n;i++)
	{
		printf("%d %lld\n",i,get(1,1,n,bl[i][0],br[i][0]));
	}
}
char s[10];
int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			int x,y; scanf("%d%d",&x,&y);
			link[x].push_back(y);
			link[y].push_back(x);
		}

		for (int i=1;i<=n;i++) vis[i]=0,on[i]=0;
		int root=dfs1(1,1);
		r[l[root]]=root; on[root]=1;
        for (int i=l[root];i!=root;i=l[i])  r[l[i]]=i,on[i]=1;

        tot=0;
        for (int i=1;i<=n;i++) vis[i]=0;
        bfs(root);
		for (int i=l[root];i!=root;i=l[i]) bfs(i);
        for (int k=1;k<=2;k++)
			for (int i=tot;i>=1;i--)
			{
				int v=q[i];
				if (on[v]) continue;
				int u=fa[v];
				bl[u][k]=min(bl[u][k],bl[v][k-1]);
				br[u][k]=max(br[u][k],br[v][k-1]);
			}

		init();
        int m; scanf("%d",&m);
		while(m--)
		{
			//look(n);
			scanf("%s",s);
			if (s[0]=='M')
			{
				int u,k,w; scanf("%d%d%d",&u,&k,&w);
				if (k==0) ad(bl[u][0],br[u][0],w);
				if (k==1)
				{
					ad(bl[u][0],br[u][0],w);
					ad(bl[u][1],br[u][1],w);//
					if (on[u])
					{
						int lv=l[u],rv=r[u];
						ad(bl[lv][0],br[lv][0],w);
						ad(bl[rv][0],br[rv][0],w);
					}
					else
					{
						int v=fa[u];
						ad(bl[v][0],br[v][0],w);
					}
				}
				if (k==2)
				{
					ad(bl[u][0],br[u][0],w);
					ad(bl[u][1],br[u][1],w);
					ad(bl[u][2],br[u][2],w);
					if (on[u])
					{
						int lv=l[u];
						ad(bl[lv][0],br[lv][0],w);
						ad(bl[lv][1],br[lv][1],w);
						int rv=r[u];
						ad(bl[rv][0],br[rv][0],w);
						ad(bl[rv][1],br[rv][1],w);
						lv=l[lv];
						if (lv!=rv)
							ad(bl[lv][0],br[lv][0],w);
						else lv=r[lv];
						rv=r[rv];
						if (rv!=lv)
							ad(bl[rv][0],br[rv][0],w);
					}
					else
					{
						int v=fa[u];
						ad(bl[v][0],br[v][0],w);
						ad(bl[v][1],br[v][1],w);
						ad(bl[u][0],br[u][0],-w);
						if (on[v])
						{
							int lv=l[v],rv=r[v];
							ad(bl[lv][0],br[lv][0],w);
							ad(bl[rv][0],br[rv][0],w);
						}
						else
						{
							v=fa[v];
							ad(bl[v][0],br[v][0],w);
						}
					}
				}
			}
			if (s[0]=='Q')
			{
				int u,k,w; scanf("%d%d",&u,&k);
				ll ret=0;
				if (k==0) ret+=gt(bl[u][0],br[u][0]);
				if (k==1)
				{
					ret+=gt(bl[u][0],br[u][0]);
					ret+=gt(bl[u][1],br[u][1]);
					if (on[u])
					{
						int lv=l[u],rv=r[u];
						ret+=gt(bl[lv][0],br[lv][0]);
						ret+=gt(bl[rv][0],br[rv][0]);
					}
					else
					{
						int v=fa[u];
						ret+=gt(bl[v][0],br[v][0]);
					}
				}
				if (k==2)
				{
					ret+=gt(bl[u][0],br[u][0]);
					ret+=gt(bl[u][1],br[u][1]);
					ret+=gt(bl[u][2],br[u][2]);
					if (on[u])
					{
						int lv=l[u];
						ret+=gt(bl[lv][0],br[lv][0]);
						ret+=gt(bl[lv][1],br[lv][1]);
						int rv=r[u];
						ret+=gt(bl[rv][0],br[rv][0]);
						ret+=gt(bl[rv][1],br[rv][1]);
						lv=l[lv];
						if (lv!=rv)
							ret+=gt(bl[lv][0],br[lv][0]);
						else lv=r[lv];
						rv=r[rv];
						if (rv!=lv)
							ret+=gt(bl[rv][0],br[rv][0]);
					}
					else
					{
						int v=fa[u];
						ret+=gt(bl[v][0],br[v][0]);
						ret+=gt(bl[v][1],br[v][1]);
						ret-=gt(bl[u][0],br[u][0]);
						if (on[v])
						{
							int lv=l[v],rv=r[v];
							ret+=gt(bl[lv][0],br[lv][0]);
							ret+=gt(bl[rv][0],br[rv][0]);
						}
						else
						{
							v=fa[v];
							ret+=gt(bl[v][0],br[v][0]);
						}
					}
				}
				printf("%lld\n",ret);
			}

		}

		for (int i=1;i<=n;i++) link[i].clear();
	}
}
/*
1
8
1 2
2 3
3 4
1 4
2 5
3 6
5 7
5 8
12
MODIFY 8 1 5
MODIFY 8 2 2
QUERY 5 0
QUERY 5 1
QUERY 5 2
MODIFY 7 2 2
QUERY 7 2
MODIFY 3 1 5
MODIFY 2 2 2
QUERY 6 1
MODIFY 4 1 -2
QUERY 2 2
*/

 

Avatar_small
Rajasthan Board Ques 说:
2022年8月20日 23:53 Rajasthan Board Model Paper 2023 Class 5 Pdf Download with Answers for Rajasthani Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Rajasthan Board Question Paper Class 5 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.
Avatar_small
Rajasthan Board Ques 说:
2022年8月20日 23:54

Rajasthan Board Model Paper 2023 Class 5 Pdf Download with Answers for Rajasthani Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Rajasthan Board Question Paper Class 5 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

Avatar_small
Find PC Serial Numbe 说:
2022年12月20日 02:28

Windows computers, by default, cannot view their PC or Laptop Serial number by staring at the system interface or using recognized system information tools. However, the serial number may still be found using the Command Prompt, a built-in tool in every Microsoft operating system. Find PC Serial Number Microsoft has issued A Serial Number, Device ID, Product ID and etc is a unique identifying number issued by the original equipment of Windows devices.

Avatar_small
BSNL FTTH 说:
2023年2月07日 21:08

BSNL is installing Bharat Net a country-wide fiber optic cable for internet connectivity in many of the panchayats, and on the other hand, ISP brought the same fibernet technology to your doorstep directly and through TIPs. BSNL FTTH Telecom Infrastructure Providers (TIPs) with new BSNL Fiber plans covering many isolated pockets in all BSNL circles of the country for 50Mbps to 300 Mbps internet speed on providing with BSNL Fiber Plans along with FREE ONT as per the possibility.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter