mcfx's blog - 分治

mcfx's blog - 分治 2017-01-08T00:20:00+08:00 Typecho /feed/atom/category/fz/ <![CDATA[BZOJ 2989: 数列 & 4170: 极光]]> /archives/163/ 2017-01-08T00:20:00+08:00 2017-01-08T00:20:00+08:00 admin

###Description
给定一个长度为n的正整数数列a[i]。
定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。
2种操作（k都是正整数）：
1.Modify x k：将第x个数的值修改为k。
2.Query x k：询问有几个i满足graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。（某位置多次修改为同样的数值，按多次统计）

###Input
第1行两个整数n,q。分别表示数列长度和操作数。
第2行n个正整数，代表初始数列。
第3--q+2行每行一个操作。

###Output
对于每次询问操作，输出一个非负整数表示答案

###Sample Input
3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1

###Sample Output
2
3
3

###HINT
N<=60000 修改操作数<=40000 询问<=60000 Max{a[i]}含修改<=100000

###Solution
这道题其实是维护两种操作，向平面上加点，查询菱形内点数
把(x,y)变为(x+y,x-y)，菱形就变成了正方形
假设某个询问是以(x0,y0)为中心，边长为2k的正方形，那么可以拆成两个，一个是x>=x0-k且x<=x0+k且y<=y0+k的点数，另一个是x>=x0-k且x<=x0+k且y<y0-k的点数，把两个询问做差就和原询问相同
那么可以CDQ分治，按y排序，x用树状数组维护

###Code
```c++
#include<bits/stdc++.h>

using namespace std;

int n,m,s[60001],ans[60000],ac,qc,mx;

struct query
{
	int x,y,k,id;char op;
}q[230000],tmp[230000];

inline void add(int x,int y){q[qc].x=x+y,q[qc].y=x-y,qc++,mx=max(mx,x+y);}

int p[160001];
inline void pl(int x){for(;x<=mx;x+=x&-x)p[x]++;}
inline int qr(int x){if(x<=0)return 0;int r=0;for(x=min(x,mx);x;x^=x&-x)r+=p[x];return r;}
inline void cl(int x){for(;x<=mx;x+=x&-x)p[x]=0;}

void work(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	work(l,mid),work(mid+1,r);
	int i1=l,i2=mid+1,ti=l;
	for(;i2<=r;tmp[ti++]=q[i2++])
	{
		for(;i1<=mid&&q[i1].y<=q[i2].y;tmp[ti++]=q[i1++])
			if(!q[i1].op)pl(q[i1].x);
		if(q[i2].op)
		{
			if(q[i2].op==1)
				ans[q[i2].id]+=qr(q[i2].x+q[i2].k)-qr(q[i2].x-q[i2].k-1);
			else
				ans[q[i2].id]+=qr(q[i2].x-q[i2].k-1)-qr(q[i2].x+q[i2].k);
		}
	}
	for(;i1<=mid;tmp[ti++]=q[i1++]);
	for(i1=l;i1<=mid;i1++)if(!q[i1].op)cl(q[i1].x);
	for(i1=l;i1<=r;i1++)q[i1]=tmp[i1];
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",s+i),add(i,s[i]);
	char tmp[10];int a,b;
	while(m--)
	{
		scanf("%s%d%d",tmp,&a,&b);
		if(tmp[0]=='M')
			add(a,s[a]=b);
		else
		{
			int x=a+s[a],y=a-s[a];
			q[qc].x=x,q[qc].y=y+b,q[qc].k=b,q[qc].id=ac,q[qc].op=1,qc++;
			q[qc].x=x,q[qc].y=y-b-1,q[qc].k=b,q[qc].id=ac,q[qc].op=2,qc++;
			ac++;
		}
	}
	work(0,qc-1);
	for(int i=0;i<ac;i++)
		printf("%d\n",ans[i]);
}
```

]]> <![CDATA[BZOJ 3993: [SDOI2015]星际战争]]> /archives/63/ 2016-10-26T23:55:00+08:00 2016-10-26T23:55:00+08:00 admin

###Description
3333年，在银河系的某星球上，X军团和Y军团正在激烈地作战。在战斗的某一阶段，Y军团一共派遣了N个巨型机器人进攻X军团的阵地，其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时，这个巨型机器人就被摧毁了。X军团有M个激光武器，其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。Y军团看到自己的巨型机器人被X军团一个一个消灭，他们急需下达更多的指令。为了这个目标，Y军团需要知道X军团最少需要用多长时间才能将Y军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。

###Input
第一行，两个整数，N、M。
第二行，N个整数，A1、A2…AN。
第三行，M个整数，B1、B2…BM。
接下来的M行，每行N个整数，这些整数均为0或者1。这部分中的第i行的第j个整数为0表示第i个激光武器不可以攻击第j个巨型机器人，为1表示第i个激光武器可以攻击第j个巨型机器人。

###Output
一行，一个实数，表示X军团要摧毁Y军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过10-3即视为正确。

###Sample Input
2 2
3 10
4 6
0 1
1 1

###Sample Output
1.300000

###HINT
战斗开始后的前0.5秒，激光武器1攻击2号巨型机器人，激光武器2攻击1号巨型机器人。1号巨型机器人被完全摧毁，2号巨型机器人还剩余8的装甲值；
接下来的0.8秒，激光武器1、2同时攻击2号巨型机器人。2号巨型机器人被完全摧毁。
对于全部的数据，1<=N, M<=50，1<=Ai<=105，1<=Bi<=1000，输入数据保证X军团一定能摧毁Y军团的所有巨型机器人

###Solution
考虑二分答案，假设当前答案为time，那么从源点到Bi连容量为time*Bi的边，从Ai到汇点连容量为Ai的边，Bi,Ai间连inf，跑最大流即可

###Code
```c++
#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back

const int N=200,M=3000;

struct edge
{
	int to,ne;
	double w;
}e[M*2+2];

int p[N+1],em=2,dep[N+1],q[N],qe,fa[N+1];
double fl[N+1];
bool vis[N+1];

inline void add(int a,int b,double w)
{
	e[em].to=b,e[em].w=w,e[em].ne=p[a],p[a]=em++;
	e[em].to=a,e[em].w=0,e[em].ne=p[b],p[b]=em++;
}

bool dfs(int s,int t)
{
	if(s==t)return 1;
	for(int j=p[s];j;j=e[j].ne)
		if(!vis[e[j].to]&&e[j].w&&dep[e[j].to]>dep[s])
		{
			vis[e[j].to]=1;
			fl[e[j].to]=min(e[j].w,fl[s]);
			fa[e[j].to]=j^1;
			if(dfs(e[j].to,t))return 1;
		}
	return 0;
}

inline double dinic(int s,int t)
{
	double flow=0;
	while(1)
	{
		memset(dep,0,sizeof(dep));
		q[0]=s,qe=1,dep[s]=1;
		for(int i=0;i^qe;i++)
		{
			for(int j=p[q[i]];j;j=e[j].ne)
				if(!dep[e[j].to]&&e[j].w)
				{
					dep[e[j].to]=dep[q[i]]+1;
					q[qe++]=e[j].to;
				}
		}
		if(!dep[t])break;
		while(1)
		{
			memset(vis,0,sizeof(vis));
			fl[s]=0x7fffffff;
			dfs(s,t);
			if(!vis[t])break;
			flow+=fl[t];
			for(int i=t;i!=s;i=e[fa[i]].to)
				e[fa[i]].w+=fl[t],e[fa[i]^1].w-=fl[t];
		}
	}
	return flow;
}

int n,m,a[50],b[50],atk[50][50];

inline bool judge(double time)
{
	int s=n+m,t=n+m+1;
	memset(p,0,sizeof(p));
	em=2;
	double s1=0,s2;
	for(int i=0;i<m;i++)
		add(s,i,time*b[i]);
	for(int i=0;i<n;i++)
		add(i+m,t,a[i]),s1+=a[i];
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			if(atk[i][j])
				add(i,j+m,1e20);
	s2=dinic(s,t);
	if(abs(s1-s2)<1e-4)return 1;else return 0;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%d",a+i);
	for(int i=0;i<m;i++)
		scanf("%d",b+i);
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
		{
			int k;
			scanf("%d",&k);
			atk[i][j]=k;
		}
	double l=0,r=1e4;
	while(r-l>1e-4)
	{
		if(judge((l+r)/2))
			r=(l+r)/2;
		else
			l=(l+r)/2;
	}
	printf("%.6lf\n",r);
}
```

]]>