分类算法下的文章

BZOJ 2432: [Noi2011]兔农

December 20, 2016

###Description
农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。
问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子？
聪明的你可能已经发现，第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂什么是Fibonacci数，但他也发现了规律：第i+2个月的兔子数等于第i个月的兔子数加上第i+1个月的兔子数。前几个月的兔子数依次为：
1 1 2 3 5 8 13 21 34 …
栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。
每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每k对兔子围成一圈，最后剩下的不足k对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。
我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当k=7时，前几个月的兔子数依次为：
1 1 2 3 5 7 12 19 31 49 80 …
给定n，你能帮助栋栋计算第n个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第n个月的兔子对数除p的余数即可。

###Input
输入一行，包含三个正整数n, k, p。

###Output
输出一行，包含一个整数，表示栋栋第n个月的兔子对数除p的余数。

###Sample Input
6 7 100

###Sample Output
7

###Solution
按模k余数写出数列，则为
1,1,...,a,0,
a,a,...,b,0,
b,b,...,c,0,
...
这个数列最后有可能每一排首项循环，也有可能不再出现0
每次求a的逆元，则其在fib数列中首次出现位置就是a后面下一个0的位置，如果没有0特判

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

typedef long long ll;

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)

void exgcd(int a,int b,int &x,int &y){if(b)exgcd(b,a%b,y,x),y-=(a/b)*x;else x=1,y=0;}

ll n;
int k,p,pos[1000000],f[6000010]={0,1,1},p2[1000000];

struct mat
{
	int a[3][3];
	inline void operator *=(mat x)
	{
		ll t[3][3];memset(t,0,sizeof(t));
		fo0(i,3)fo0(j,3)fo0(k,3)t[i][k]+=(ll)a[i][j]*x.a[j][k];
		fo0(i,3)fo0(j,3)a[i][j]=t[i][j]%p;
	}
	inline mat operator *(mat x)
	{
		mat r=*this;r*=x;return r;
	}
};

mat pow(mat a,ll p)
{
	mat r=(mat){1,0,0,0,1,0,0,0,1};
	for(;p;p>>=1,a*=a)if(p&1)r*=a;
	return r;
}

struct data
{
	int st,len;mat x;
}s[1000001];

inline mat get(ll n,int tt)
{
	mat r=(mat){1,0,0,0,1,0,0,0,1};
	if(!n)return r;
	for(;n>=s[tt].len;n-=s[tt++].len)r*=s[tt].x;
	return r*pow((mat){0,1,0,1,1,0,0,0,1},n);
}

int main()
{
	scanf("%lld%d%d",&n,&k,&p);
	for(int i=3;;i++)
	{
		f[i]=f[i-1]+f[i-2];
		if(f[i]>=k)f[i]-=k;
		if(!pos[f[i]])pos[f[i]]=i;
		if(f[i]==1&&f[i-1]==0)break;
	}
	int ns=1,sc=1;
	for(;!p2[ns];sc++)
	{
		s[sc].st=ns;
		p2[ns]=sc;
		int t1,t2;
		exgcd(k,ns,t1,t2);
		if(t2<0)t2+=k;
		t1=pos[t2];
		if((ll)ns*t2%k!=1||!t1)break;
		s[sc].len=t1;
		s[sc].x=pow((mat){0,1,0,1,1,0,0,0,1},t1-1)*(mat){0,1,0,1,1,0,0,-1,1};
		ns=(ll)ns*f[t1-1]%k;
	}
	mat bfm=(mat){1,0,0,0,1,0,0,0,1},lpm=(mat){1,0,0,0,1,0,0,0,1},ans=(mat){1,0,0,0,1,0,0,0,1};
	ll bf=0,lp=0;
	fo1(i,p2[ns]-1)bf+=s[i].len,bfm*=s[i].x;
	fo(i,p2[ns],sc-1)lp+=s[i].len,lpm*=s[i].x;
	if(!lp)lp=1,lpm=(mat){0,1,0,1,1,0,0,0,1};
	if(n<bf)
	{
		ans*=get(n,1);
	}
	else
	{
		ans*=bfm;n-=bf;
		ans*=pow(lpm,n/lp);
		ans*=get(n%lp,p2[ns]);
	}
	int a1=ans.a[0][1]+ans.a[2][1];
	while(a1>=p)a1-=p;while(a1<0)a1+=p;
	printf("%d\n",a1);
}
```

BZOJ 3552: 最右非零的数

December 16, 2016

BZOJ 4539: [Hnoi2016]树

December 16, 2016

###Description
小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b，其中1<=a<=N，1<=b<=当前大树的结点数。（2.2）将模板树中以结点a为根的子树复制一遍，挂到大树中结点b的下方(也就是说，模板树中的结点a为根的子树复制到大树中后，将成为大树中结点b的子树)。（2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有L个结点，模板树中以a为根的子树共有C个结点，那么新加入模板树的C个结点在大树中的编号将是L+1,L+2,…,L+C；大树中这C个结点编号的大小顺序和模板树中对应的C个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图：
![11(4).png][1]
根据第(1)步，初始的大树与模板树是相同的。在(2.1)步，假设选择了a=4，b=3。运行(2.2)和(2.3)后，得到新的大树如下图所示
![22(2).png][2]
现在他想问你，树中一些结点对的距离是多少。

###Input
第一行三个整数：N,M,Q，以空格隔开，N表示模板树结点数，M表示第(2)中的循环操作的次数，Q 表示询问数量。接下来N-1行，每行两个整数 fr,to，表示模板树中的一条树边。再接下来M行，每行两个整数x,to，表示将模板树中 x 为根的子树复制到大树中成为结点to的子树的一次操作。再接下来Q行，每行两个整数fr,to，表示询问大树中结点 fr和 to之间的距离是多少。N,M,Q<=100000

###Output
输出Q行，每行一个整数，第 i行是第 i个询问的答案。

###Sample Input
5 2 3
1 4
1 3
4 2
4 5
4 3
3 2
6 9
1 8
5 3

###Sample Output
6
3
3

###Solution
先对模板树求lca，并按dfs序建一棵主席树
每次向大树上加子树时，先二分查找他的父亲在哪一块，然后在主席树上查接到哪个节点下面
对于每一块，存它的根节点与根节点的父亲在模板树中的编号
然后把每一块视做节点，可以得到一棵大树，对大树也求lca
处理查询时，需要分3种情况：在同一块中，两块在一条链上，两块不在一条链上

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

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#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;}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))

#define N 100000

namespace zx
{
	struct node
	{
		int lc,rc,cnt;
	}s[2000000];
	
	int sm=1;
	
	int modify(int x,int l,int r,int p)
	{
		int t=sm++;
		s[t]=s[x];
		s[t].cnt++;
		if(l^r)
		{
			int f=(l+r)>>1;
			if(p<=f)
				s[t].lc=modify(s[x].lc,l,f,p);
			else
				s[t].rc=modify(s[x].rc,f+1,r,p);
		}
		return t;
	}
	
	int kth(int a,int b,int l,int r,int k)
	{
		if(l==r)return l;
		int t=s[s[a].lc].cnt-s[s[b].lc].cnt,f=(l+r)>>1;
		if(t>=k)return kth(s[a].lc,s[b].lc,l,f,k);
		return kth(s[a].rc,s[b].rc,f+1,r,k-t);
	}
	
	int root[N+1];
}

int n,m,q;

namespace t1
{
	int p[N+1],idm,id[N+1],idr[N+1],fa[N+1][17],dep[N+1],sz[N+1];
	
	struct edge
	{
		int to,ne;
	}e[N<<1];
	
	inline void add(int x,int a,int b)
	{
		e[x].to=b,e[x].ne=p[a],p[a]=x;
	}
	
	void dfs(int x)
	{
		sz[x]=1;
		id[x]=++idm;
		zx::root[id[x]]=zx::modify(zx::root[id[x]-1],1,n,x);
		for(int i=p[x];i;i=e[i].ne)
			if(e[i].to^fa[x][0])
				fa[e[i].to][0]=x,dep[e[i].to]=dep[x]+1,dfs(e[i].to),sz[x]+=sz[e[i].to];
		idr[x]=idm;
	}
	
	inline int dis(int x,int y)
	{
		int a=x,b=y,ret=0;
		if(dep[a]<dep[b])
		{
			for(int i=16;~i;i--)
				if((dep[b]-dep[a])&(1<<i))
					ret+=1<<i,b=fa[b][i];
		}
		else if(dep[a]>dep[b])
		{
			for(int i=16;~i;i--)
				if((dep[a]-dep[b])&(1<<i))
					ret+=1<<i,a=fa[a][i];
		}
		if(a==b)return ret;
		for(int i=16;~i;i--)
			if(fa[a][i]^fa[b][i])
				a=fa[a][i],b=fa[b][i],ret+=1<<i+1;
		return ret+2;
	}
}

namespace t2
{
	int cnt=1;
	ll id[N+1],nid;
	
	struct data
	{
		int a,b,dep,fa[17],di[17];
	}s[N+1];
	
	inline void link(int a,ll b)
	{
		int c=std::upper_bound(id,id+cnt,b)-id-1;
		int cf=s[c].a,d=zx::kth(zx::root[t1::idr[cf]],zx::root[t1::id[cf]-1],1,n,b-id[c]+1);
		s[cnt].a=a;
		s[cnt].b=d;
		s[cnt].dep=s[c].dep+1;
		s[cnt].fa[0]=c;
		s[cnt].di[0]=t1::dis(cf,d)+1;
		id[cnt]=nid;
		nid+=t1::sz[a];
		cnt++;
	}
	
	inline void init()
	{
		for(int i=0;i<16;i++)
			for(int j=0;j<cnt;j++)
				s[j].fa[i+1]=s[s[j].fa[i]].fa[i],s[j].di[i+1]=s[j].di[i]+s[s[j].fa[i]].di[i];
	}
	
	inline int lca(int x,int y)
	{
		int a=x,b=y;
		if(s[a].dep<s[b].dep)
		{
			for(int i=16;~i;i--)
				if((s[b].dep-s[a].dep)&(1<<i))
					b=s[b].fa[i];
		}
		else if(s[a].dep>s[b].dep)
		{
			for(int i=16;~i;i--)
				if((s[a].dep-s[b].dep)&(1<<i))
					a=s[a].fa[i];
		}
		if(a==b)return a;
		for(int i=16;~i;i--)
			if(s[a].fa[i]^s[b].fa[i])
				a=s[a].fa[i],b=s[b].fa[i];
		return s[a].fa[0];
	}
	
	inline ll linkdis(int p,int q,int x,int y)
	{
		ll ret=t1::dis(x,s[p].a)+1;
		for(int i=16;~i;i--)
			if((s[p].dep-s[q].dep-1)&(1<<i))
				ret+=s[p].di[i],p=s[p].fa[i];
		return ret+t1::dis(s[p].b,y);
	}
	
	inline ll dis(ll x,ll y)
	{
		int p=std::upper_bound(id,id+cnt,x)-id-1,q=std::upper_bound(id,id+cnt,y)-id-1;
		int xid=zx::kth(zx::root[t1::idr[s[p].a]],zx::root[t1::id[s[p].a]-1],1,n,x-id[p]+1);
		int yid=zx::kth(zx::root[t1::idr[s[q].a]],zx::root[t1::id[s[q].a]-1],1,n,y-id[q]+1);
		if(p==q)return t1::dis(xid,yid);
		int t=lca(p,q);
		if(t==p)return linkdis(q,p,yid,xid);
		if(t==q)return linkdis(p,q,xid,yid);
		ll ret=t1::dis(xid,s[p].a)+t1::dis(yid,s[q].a)+2;
		for(int i=16;~i;i--)
			if((s[p].dep-s[t].dep-1)&(1<<i))
				ret+=s[p].di[i],p=s[p].fa[i];
		for(int i=16;~i;i--)
			if((s[q].dep-s[t].dep-1)&(1<<i))
				ret+=s[q].di[i],q=s[q].fa[i];
		return ret+t1::dis(s[p].b,s[q].b);
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		t1::add(i<<1,a,b);
		t1::add(i<<1|1,b,a);
	}
	zx::root[0]=zx::sm++;
	t1::fa[1][0]=1;
	t1::dfs(1);
	for(int i=0;i<16;i++)
		for(int j=1;j<=n;j++)
			t1::fa[j][i+1]=t1::fa[t1::fa[j][i]][i];
	t2::s[0].a=1;
	t2::id[0]=1;
	t2::nid=n+1;
	while(m--)
	{
		int a;
		ll b;
		scanf("%d%lld",&a,&b);
		t2::link(a,b);
	}
	t2::init();
	while(q--)
	{
		ll a,b;
		scanf("%lld%lld",&a,&b);
		printf("%lld\n",t2::dis(a,b));
	}
}
```

[1]: /usr/uploads/2016/12/1348856476.png
  [2]: /usr/uploads/2016/12/2791822739.png

BZOJ 4700: 适者

December 1, 2016

###Description
敌方有n台人形兵器，每台的攻击力为Ai，护甲值为Di。我方只有一台人形兵器，攻击力为ATK。战斗看作回合制，
每回合进程如下：
·1 我方选择对方某台人形兵器并攻击，令其护甲值减少ATK，若护甲值<0则被破坏。
·2 敌方每台未被破坏的人形兵器攻击我方基地造成Ai点损失。
但是，在第一回合开始之前，某两台敌方的人形兵器被干掉了(秒杀）。问最好情况下，我方基地会受到多少点损
失。

###Input
第一行两个数n，ATK，表示敌方人形兵器数量和我方人形兵器攻击力。
接下来n行，每行两个数A，Di，表示对方第i台人形兵器的攻击力和护甲值。
3<=n<=3×10^5，Ai，Di<=10^4，ATK<10^4

###Output
只一行，一个数，表示最好情况下我方基地会受到的损失总和。

###Sample Input
3 7
30 8
7 35
1 209

###Sample Output
28

###Solution
每个敌人被杀所需时间为 Ti=Di/atk+1
设T的前缀和为P，A的后缀和为S
假设没有秒杀，按Ti/Ai排序后依次杀即可，每个敌人对答案的贡献为Si\*Ti-Ai
假设（排序后）秒杀了i和j（假设i<j）
那么我方损失会减少 Si\*Ti + P(i-1)\*Ai - Ai + Sj\*Tj + P(j-1)\*Aj - Aj - Ti\*Aj
注意最后 -Ti\*Aj 是因为算了两次
由于只有 Ti\*Aj 与 i,j 均有关，这个表达式可以看成一个以Ti为变量的一次函数
若从后往前扫，就可以看成动态维护一些直线的凸包
这个用线段树就可以维护，每个节点存一条直线，标记永久化
修改时，找到两直线交点，把距端点更短的一部分pushdown
查询时把路径上所有节点取max

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

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#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;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))

struct line
{
	ll k,b;
}s[35000];

void modify(int x,int l,int r,line p)
{
	if(s[x].k==p.k)
	{
		repr(s[x].b,p.b);
		return;
	}
	int t=(l+r)>>1;
	db f=(db)(p.b-s[x].b)/(s[x].k-p.k);
	if(f<l||f>r||l==r)
	{
		if(p.k*t+p.b>s[x].k*t+s[x].b)s[x]=p;
		return;
	}
	if(f<t+0.5)
	{
		if(p.k*r+p.b>s[x].k*r+s[x].b)std::swap(s[x],p);
		modify(x<<1,l,t,p);
	}
	else
	{
		if(p.k*l+p.b>s[x].k*l+s[x].b)std::swap(s[x],p);
		modify(x<<1|1,t+1,r,p);
	}
}

ll query(int x,int l,int r,int p)
{
	ll ret=s[x].k*p+s[x].b;
	if(l!=r)
	{
		int t=(l+r)>>1;
		if(p<=t)
			repr(ret,query(x<<1,l,t,p));
		else
			repr(ret,query(x<<1|1,t+1,r,p));
	}
	return ret;
}

struct yjq
{
	int a,t;
	ll as,tp;
	inline bool operator <(const yjq &x)const
	{
		return (ll)x.a*t<(ll)a*x.t;
	}
}p[300000];

int n,atk;

int main()
{
	scanf("%d%d",&n,&atk);
	for(int i=0;i<n;i++)
		scanf("%d%d",&p[i].a,&p[i].t),p[i].t=(p[i].t-1)/atk+1;
	std::sort(p,p+n);
	for(int i=1;i<n;i++)
		p[i].tp=p[i-1].tp+p[i-1].t;
	p[n-1].as=p[n-1].a;
	for(int i=n-2;i>=0;i--)
		p[i].as=p[i+1].as+p[i].a;
	for(int i=0;i<35000;i++)
		s[i].b=-1e18;
	ll ta=0;
	for(int i=n-1;i>=0;i--)
	{
		ll tmp=p[i].as*p[i].t+p[i].tp*p[i].a-p[i].a;
		repr(ta,query(1,1,10000,p[i].t)+tmp);
		modify(1,1,10000,(line){-p[i].a,tmp});
	}
	ll ans=0;
	for(int i=0;i<n;i++)
		ans+=p[i].as*p[i].t-p[i].a;
	ans-=ta;
	printf("%lld\n",ans);
}
```

BZOJ 3113: Toy

November 29, 2016

###Description
外面有一圈N个结点，中心有一个结点与N个结点都相连，总共就是2*N条边，删除N条边，使N+1个点连通，旋转相同视为等价，问有多少种情况。
![1.jpg][1]

###Input
输入N，M
3<=N<=10^9, 2<=M<=10^9

###Output
输出方案数 Mod M的结果

###Sample Input
3 10000
4 10000
4 10

###Sample Output
6
13
3

###Solution
考虑burnside引理，假设分成d块，那么每块的方案数是和bzoj1002一样的，可以用公式 f(n+1) = 3\*f(n) - f(n-1) + 2 计算
所以得到这个公式：1/n\*Sum_{d divides n} phi(n/d)*f(d)
于是直接根号n枚举d，然后根号d求phi，矩阵快速幂求f

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

typedef long long ll;
typedef long double ldb;

ll mod;

inline ll fm(ll x,ll y)
{
	ll tmp=(x*y-(ll)((ldb)x/mod*y+1e-8)*mod);
	return tmp<0?tmp+mod:tmp;
}

inline void mul(ll (&a)[3][3],ll (&b)[3][3],ll (&c)[3][3])
{
	ll t[3][3]={{0,0,0},{0,0,0},{0,0,0}};
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
				t[i][k]+=fm(a[i][j],b[j][k]);
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			c[i][j]=t[i][j]%mod;
}

inline ll f(int x)
{
	if(x<=1)return x;
	x--;
	ll a[3][3]={{1,0,2},{0,0,mod-1},{0,1,3}},b[3][3]={{1,0,0},{0,1,0},{0,0,1}};
	for(int i=1;i<=x;i<<=1)
	{
		if(i&x)mul(b,a,b);
		mul(a,a,a);
	}
	ll ret=b[0][2]+b[2][2];
	if(ret>=mod)return ret-mod;return ret;
}

inline int phi(int x)
{
	int t=x;
	for(int i=2;i*i<=x;i++)
		if(x%i==0)
		{
			t/=i,t*=i-1;
			x/=i;
			while(x%i==0)x/=i;
		}
	if(x>1)t/=x,t*=x-1;
	return t;
}

int main()
{
	int n;
	while(~scanf("%d%lld",&n,&mod))
	{
		mod*=n;
		ll a2=0;
		for(int i=1;i*i<=n;i++)
			if(n%i==0)
			{
				if(i*i==n)
				{
					a2+=fm(phi(i),f(i));
				}
				else
				{
					a2+=fm(phi(i),f(n/i))+fm(phi(n/i),f(i));
				}
				a2%=mod;
			}
		printf("%lld\n",a2/n);
	}
}
```

[1]: /usr/uploads/2016/11/709092212.jpg

BZOJ 4722: 由乃

November 27, 2016

###Description
给一个长为n的序列a，每个数在0到v - 1之间，有m次操作。
操作1：每次询问一个区间中是否可以选出两个下标的集合X，Y，满足：
1.X和Y没有交集
2.设集合X中有一个元素是i，则其对集合X的贡献是a[i] + 1，要求集合X的元素的总贡献和集合Y的元素的总贡献
相等如果可以选出这两个集合，输出 Yuno否则输出 Yuki
操作2：修改一个区间l,r之间的数，使得所有l <= i <= r，a[i] = a[i] \* a[i] \* a[i] % v ，即区间立方

###Input
第一行三个数n , m , v，意义如题所述
之后一行n个数，表示序列a
之后m行每行三个数opt , l , r，表示操作类型是1还是2，操作的区间是[l , r]

###Output
m行，每行一个字符串 Yuno 或者 Yuki 表示能否选出这两个集合

###Sample Input
20 20 152
3 26 133 54 79 81 72 109 66 91 82 100 35 23 104 17 51 114 12 58
2 1 17
2 6 12
1 1 12
2 3 5
2 11 11
2 7 19
2 6 15
1 5 12
1 1 9
1 10 19
2 3 19
2 6 20
2 1 13
2 1 15
2 1 9
1 1 1
2 1 7
2 7 19
2 6 19
2 3 6

###Sample Output
Yuno
Yuno
Yuno
Yuno
Yuki

###HINT
总算在bzoj上出题了呀
这下可以安心退役了~
总共有10组数据
对于100%的数据，n , m <= 100000 , v <= 1000,数据没有梯度

###Solution
当某个区间长度大于13一定有解，小于13 bitset乱搞
立方操作树状数组区间加，取数时倍增

###Code
```c++
#include<bits/stdc++.h>
int n,m,v,u,s[100001],p[100001],N[1000][17],i,j,O,l,r,t,T;
main()
{
	scanf("%d%d%d",&n,&m,&v);
	while((1<<u)<=v)u++;
	for(;i<v;i++)
		N[i][0]=1ll*i*i*i%v;
	for(i=1;i<=n;i++)
		scanf("%d",s+i);
	for(i=0;i<16;i++)
		for(j=0;j<v;j++)
			N[j][i+1]=N[N[j][i]][i];
	while(m--)
	{
		scanf("%d%d%d",&O,&l,&r);
		if(O&1)
		{
			if(r-l>=u)puts("Yuno");
			else
			{
				std::bitset<10360> x(1);
				for(i=l;i<=r;i++)
				{
					t=0,T=s[i];
					for(j=i;j;j^=j&-j)t+=p[j];
					for(j=0;j<17;j++)if((t>>j)&1)T=N[T][j];
					if((x&(x<<T+1)).any())
					{
						puts("Yuno");
						goto Y;
					}
					x|=x<<T+1;
				}
				puts("Yuki");
				Y:;
			}
		}
		else
		{
			for(i=l;i<=n;i+=i&-i)p[i]++;
			for(i=r+1;i<=n;i+=i&-i)p[i]--;
		}
	}
}
```

BZOJ 3343: 教主的魔法分块

November 15, 2016

###Description
教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。
每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）
CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。
WD巨懒，于是他把这个回答的任务交给了你。

###Input
第1行为两个整数N、Q。Q为问题数与教主的施法数总和。
第2行有N个正整数，第i个数代表第i个英雄的身高。
第3到第Q+2行每行有一个操作：
（1）若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。
（2）若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。

###Output
对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。

###Sample Input
5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

###Sample Output
2
3

###HINT
【输入输出样例说明】
原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4。
【数据范围】
对30%的数据，N≤1000，Q≤1000。
对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。

###Solution
分块可以做，然而花式分块更快。。
在每个操作的端点处划分，共分为最多4Q块，那么每个操作必会在一段连续块上
处理每块时，遍历所有包含它的操作，若为修改，则delta+=w，若为查询，则记录c-delta，然后将询问按c-delta排序
之后遍历该块中的数，二分+差分维护贡献
时间复杂度$$O(Q^2logQ+NlogQ)$$

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

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#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;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))
#define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d)

int n,m,h[1000001],q[3000][4],bl[12010],ans[3000],tmp[3000];

struct yjq
{
	int x,id;
	inline bool operator <(const yjq &p)const
	{
		return x<p.x;
	}
}f[3000];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%d",h+i);
	int bc=2;
	bl[0]=n-1;
	bl[1]=-1;
	for(int i=0;i<m;i++)
	{
		char opt[2];
		scanf("%s%d%d%d",opt,&q[i][1],&q[i][2],&q[i][3]);
		q[i][1]--,q[i][2]--;
		q[i][0]=opt[0]=='A';
		bl[bc++]=q[i][1]-1;
		bl[bc++]=q[i][2];
	}
	std::sort(bl,bl+bc);
	bc=std::unique(bl,bl+bc)-bl;
	for(int i=1;i<bc;i++)
	{
		bl[i-1]++;
		int delta=0,fm=0;
		for(int j=0;j<m;j++)
			if(q[j][1]<=bl[i-1]&&q[j][2]>=bl[i])
			{
				if(q[j][0]==0)
					delta+=q[j][3];
				else
					f[fm].x=q[j][3]-delta,f[fm++].id=j;
			}
		std::sort(f,f+fm);
		memset(tmp,0,sizeof(tmp));
		for(int j=bl[i-1];j<=bl[i];j++)
		{
			if(f[0].x>h[j])continue;
			int l=0,r=fm;
			while(r-l>1)
			{
				if(f[(l+r)>>1].x>h[j])
					r=(l+r)>>1;
				else
					l=(l+r)>>1;
			}
			tmp[l]++;
		}
		for(int j=fm-1,t=0;j>=0;j--)
		{
			t+=tmp[j];
			ans[f[j].id]+=t;
		}
	}
	for(int i=0;i<m;i++)
		if(q[i][0]==1)
			printf("%d\n",ans[i]);
}
```

[1]: http://mcfx.us/usr/uploads/2016/11/758503410.gif

BZOJ 3163: [Heoi2013]Eden的新背包问题

November 15, 2016

###Description
“寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心心静，能不能说给我听。”
失忆的Eden总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。 记忆中，她总是喜欢给Eden出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden这样的一个问题：有n个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱m固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过m，且价值和最大。众所周知的，这是一个很经典的多重背包问题，Eden很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次 询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。
这下Eden 犯难了，不过Eden不希望自己被难住，你能帮帮他么？

###Input
第一行一个数n，表示有n个玩偶，玩偶从0开始编号
第二行开始后面的 n行，每行三个数 ai, bi, c i，分别表示买一个第i个玩偶需要的价钱，获得的价值以及第i个玩偶的限购次数。
接下来的一行为q，表示询问次数。
接下来q行，每行两个数di. ei表示每个询问去掉的是哪个玩偶（注意玩偶从0开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立）

###Output
输出q行，第i行输出对于第 i个询问的答案。

###Sample Input
5
2 3 4
1 2 1
4 1 2
2 1 1
3 2 3
5
1 10
2 7
3 4
4 8
0 5

###Sample Output
13
11
6
12
4

###Solution
多重背包+分治背包
递归处理[l,r)，每次加入左半部分的点，处理右边，再加入右边，处理左边
时间复杂度$$O(n^2log^2n+q)$$

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

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#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;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))
#define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d)

struct _toy
{
	int a,b,c;
}toy[1000];

struct _qr
{
	int w,ans,ne;
}qr[300001];

int p[1000],n,q,f[11][1001];

inline void merge(int *s,int a,int b)
{
	for(int i=1000;i>=a;i--)
		repr(s[i],max(s[i-1],s[i-a]+b));
}

void solve(int l,int r,int d)
{
	if(l+1==r)
	{
		for(int i=p[l];i;i=qr[i].ne)
			qr[i].ans=f[d][qr[i].w];
	}
	else
	{
		int p=(l+r)>>1;
		memcpy(f[d+1],f[d],sizeof(f[d]));
		for(int i=l;i<p;i++)
		{
			int t=toy[i].c;
			for(int j=1;j<t;t-=j,j<<=1)
				merge(f[d+1],toy[i].a*j,toy[i].b*j);
			merge(f[d+1],toy[i].a*t,toy[i].b*t);
		}
		solve(p,r,d+1);
		memcpy(f[d+1],f[d],sizeof(f[d]));
		for(int i=p;i<r;i++)
		{
			int t=toy[i].c;
			for(int j=1;j<t;t-=j,j<<=1)
				merge(f[d+1],toy[i].a*j,toy[i].b*j);
			merge(f[d+1],toy[i].a*t,toy[i].b*t);
		}
		solve(l,p,d+1);
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d%d",&toy[i].a,&toy[i].b,&toy[i].c);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int x;
		scanf("%d%d",&x,&qr[i].w);
		qr[i].ne=p[x];
		p[x]=i;
	}
	solve(0,n,0);
	for(int i=1;i<=q;i++)
		printf("%d\n",qr[i].ans);
}
```

BZOJ 3038: 上帝造题的七分钟2

November 9, 2016

###Description
XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。
"第一分钟，X说，要有数列，于是便给定了一个正整数数列。
第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟，k说，要能查询，于是便有了求一段数的和的操作。
第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。
第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。
第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。"
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。

###Input
第一行一个整数n，代表数列中数的个数。
第二行n个正整数，表示初始状态下数列中的数。
第三行一个整数m，表示有m次操作。
接下来m行每行三个整数k,l,r，k=0表示给[l,r]中的每个数开平方(下取整)，k=1表示询问[l,r]中各个数的和。

###Output
对于询问操作，每行输出一个回答。

###Sample Input
10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

###Sample Output
19
7
6

###Solution
显然，一个数最多开根6次就会变成1
那么直接用线段树维护区间最大值，每次暴力修改即可

###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

int n,t=1;
ll s[270000],ma[270000];

inline void up(int x)
{
	s[x]=s[x<<1]+s[x<<1|1];
	ma[x]=max(ma[x<<1],ma[x<<1|1]);
}

void modify(int x,int l,int r,int ql,int qr)
{
	if(ma[x]<=1)return;
	if(x&t)
	{
		ma[x]=sqrt(ma[x]);
		s[x]=ma[x];
		return;
	}
	int q=(l+r)>>1;
	if(ql<q)modify(x<<1,l,q,ql,min(q,qr));
	if(qr>q)modify(x<<1|1,q,r,max(q,ql),qr);
	up(x);
}

int main()
{
	int m;
	scanf("%d",&n);
	while(t<n+2)t<<=1;
	for(int i=1;i<=n;i++)
		scanf("%lld",ma+i+t),s[i+t]=ma[i+t];
	for(int i=t-1;i;i--)
		up(i);
	scanf("%d",&m);
	while(m--)
	{
		int opt,x,y;
		scanf("%d%d%d",&opt,&x,&y);
		if(x>y)std::swap(x,y);
		if(opt==0)
		{
			modify(1,1,t,x,y+1);
		}
		else
		{
			x=x+t-1,y=y+t+1;
			ll ans=0;
			while(x^y^1)
			{
				if(~x&1)ans+=s[x^1];
				if(y&1)ans+=s[y^1];
				x>>=1,y>>=1;
			}
			printf("%lld\n",ans);
		}
	}
}
```

BZOJ 3993: [SDOI2015]星际战争

October 26, 2016

###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

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);
}
```