mcfx's blog - 2016年11月

BZOJ 3113: Toy

admin — Tue, 29 Nov 2016 23:24:00 +0800

###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: 由乃

admin — Sun, 27 Nov 2016 12:35:00 +0800

###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 3196: Tyvj 1730 二逼平衡树

admin — Thu, 17 Nov 2016 00:28:00 +0800

###Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)

###Input
第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继

###Output
对于操作1,2,4,5各输出一行，表示查询结果

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

###Sample Output
2
4
3
4
9

###HINT
1.n和m的数据范围：n,m<=50000
2.序列中每个数的数据范围：[0,1e8]
3.虽然原题没有，但事实上5操作的k可能为负数

###Solution
外层树状数组，内层值域线段树，在每个节点记count,修改时分别修改，查询时用r和l-1对应的一大堆节点做差（有点像主席树）

###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 node
{
	node *lc,*rc;
	int cnt;
	node();
}_null,*null=&_null;
node::node(){lc=rc=null;cnt=0;}
int pf;

void erase(node *x)
{
	if(x->lc!=null)erase(x->lc);
	if(x->rc!=null)erase(x->rc);
	delete x;
}

void modify(node *&x,int l,int r,int p,int v)
{
	if(x==null)x=new node;
	x->cnt+=v;
	if(!x->cnt)
	{
		erase(x);
		x=null;
		return;
	}
	if(l!=r)
	{
		int f=(l+r)/2;
		if(p<=f)
			modify(x->lc,l,f,p,v);
		else
			modify(x->rc,f+1,r,p,v);
	}
}

struct group
{
	node *x[50];
	int mul[50],sz;
	inline int cnt()
	{
		int ret=0;
		for(int i=0;i<sz;i++)ret+=x[i]->cnt*mul[i];
		return ret;
	}
	inline group* lc(group *f)
	{
		f->sz=sz;
		for(int i=0;i<sz;i++)f->x[i]=x[i]->lc,f->mul[i]=mul[i];
		return f;
	}
	inline group* rc(group *f)
	{
		f->sz=sz;
		for(int i=0;i<sz;i++)f->x[i]=x[i]->rc,f->mul[i]=mul[i];
		return f;
	}
};

int cnt(group *x,int l,int r,int ql,int qr)
{
	if(l==ql&&r==qr)return x->cnt();
	int t=(l+r)/2,ans=0;
	group ch;
	if(ql<=t)ans+=cnt(x->lc(&ch),l,t,ql,min(t,qr));
	if(qr>t)ans+=cnt(x->rc(&ch),t+1,r,max(ql,t+1),qr);
	return ans;
}

int kth(group *x,int l,int r,int rk)
{
	if(l==r)return l;
	group ch;
	x->lc(&ch);
	int lcnt;
	if((lcnt=ch.cnt())>=rk)
		return kth(&ch,l,(l+r)/2,rk);
	else
		return kth(x->rc(&ch),(l+r)/2+1,r,rk-lcnt);
}

int gmax(group *x,int l,int r,int p)
{
	if(!x->cnt())return 0;
	if(l==r)return l;
	int t=(l+r)/2;
	group ch;
	if(p<=t)return gmax(x->lc(&ch),l,t,p);
	if(r==p)
	{
		x->rc(&ch);
		if(ch.cnt())return gmax(&ch,t+1,r,p);
		return gmax(x->lc(&ch),l,t,t);
	}
	return max(gmax(x->lc(&ch),l,t,t),gmax(x->rc(&ch),t+1,r,p));
}

int gmin(group *x,int l,int r,int p)
{
	if(!x->cnt())return 0x7fffffff;
	if(l==r)return l;
	int t=(l+r)/2;
	group ch;
	if(p>t)return gmin(x->rc(&ch),t+1,r,p);
	if(l==p)
	{
		x->lc(&ch);
		if(ch.cnt())return gmin(&ch,l,t,p);
		return gmin(x->rc(&ch),t+1,r,t+1);
	}
	return min(gmin(x->lc(&ch),l,t,p),gmin(x->rc(&ch),t+1,r,t+1));
}

#define nl 0
#define nr 100000001

node *root[50001];
int v[50001];

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++)
		root[i]=new node;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",v+i);
		for(int j=i;j<=n;j+=lb(j))
			modify(root[j],nl,nr,v[i],1);
	}
	while(m--)
	{
		int opt,a,b,c;
		scanf("%d%d%d",&opt,&a,&b);
		if(opt==3)
		{
			for(int j=a;j<=n;j+=lb(j))
				modify(root[j],nl,nr,v[a],-1);
			v[a]=b;
			for(int j=a;j<=n;j+=lb(j))
				modify(root[j],nl,nr,v[a],1);
		}
		else
		{
			scanf("%d",&c);
			group tmp;
			tmp.sz=0;
			for(int j=b;j;j^=lb(j))
				tmp.mul[tmp.sz]=1,tmp.x[tmp.sz++]=root[j];
			for(int j=a-1;j;j^=lb(j))
				tmp.mul[tmp.sz]=-1,tmp.x[tmp.sz++]=root[j];
			if(opt==1)
			{
				printf("%d\n",cnt(&tmp,nl,nr,nl,min(nr,c-1))+1);
			}
			else if(opt==2)
			{
				printf("%d\n",kth(&tmp,nl,nr,c));
			}
			else if(opt==4)
			{
				printf("%d\n",gmax(&tmp,nl,nr,min(nr,c-1)));
			}
			else
			{
				printf("%d\n",gmin(&tmp,nl,nr,max(nl,c+1)));
			}
		}
	}
}
```

BZOJ 3343: 教主的魔法分块

admin — Tue, 15 Nov 2016 15:39:00 +0800

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

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的新背包问题

admin — Tue, 15 Nov 2016 08:21:00 +0800

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

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 4668: 冷战 LCT

admin — Wed, 09 Nov 2016 16:51:00 +0800

###Description
1946 年 3 月 5 日，英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”，正式拉开了冷战序幕。
美国和苏联同为世界上的“超级大国”，为了争夺世界霸权，两国及其盟国展开了数十年的斗争。在这段时期，虽然分歧和冲突严重，但双方都尽力避免世界范围的大规模战争（第三次世界大战）爆发，其对抗通常通过局部代理战争、科技和军备竞赛、太空竞争、外交竞争等“冷”方式进行，即“相互遏制，不动武力”，因此称之为“冷战”。
Reddington 是美国的海军上将。由于战争局势十分紧张，因此他需要时刻关注着苏联的各个活动，避免使自己的国家陷入困境。苏联在全球拥有 N 个军工厂，但由于规划不当，一开始这些军工厂之间是不存在铁路的，为了使武器制造更快，苏联决定修建若干条道路使得某些军工厂联通。
Reddington 得到了苏联的修建日程表，并且他需要时刻关注着某两个军工厂是否联通，以及最早在修建哪条道路时会联通。具体而言，现在总共有M 个操作，操作分为两类：
• 0 u v，这次操作苏联会修建一条连接 u 号军工厂及 v 号军工厂的铁路，注意铁路都是双向的;
• 1 u v， Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通，假如到这次操作都没有联通，则输出 0;
作为美国最强科学家， Reddington 需要你帮忙设计一个程序，能满足
他的要求。

###Input
第一行两个整数 N, M。
接下来 M 行，每行为 0 u v 或 1 u v 的形式。
数据是经过加密的，对于每次加边或询问，真正的 u, v 都等于读入的
u, v 异或上上一次询问的答案。一开始这个值为 0。
1 ≤ N, M ≤ 500000，解密后的 u, v 满足1 ≤ u, v ≤ N, u不等于v

###Output
对于每次 1 操作，输出 u, v 最早在加入哪条边后会联通，若到这个操
作时还没联通，则输出 0。

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

###Sample Output
```
0
3
5
```

###Solution
直接用LCT维护动态最小生成树就行了，虽然很暴力，但能AC

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

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
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 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 pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d)

const int N=1000001;

struct node
{
	node *c[2],*fa;
	int val,ma;
	bool rev;
	inline void rotate(bool f);
	inline void pushdown();
	inline void pushup();
}s[N],_null,*null=&_null;

inline void node::pushdown()
{
	if(fa->c[0]==this||fa->c[1]==this)
		fa->pushdown();
	if(rev)
	{
		rev=0;
		std::swap(c[0],c[1]);
		if(c[0]!=null)c[0]->rev=!c[0]->rev;
		if(c[1]!=null)c[1]->rev=!c[1]->rev;
	}
}

inline void node::rotate(bool f)
{
	fa->c[f]=c[!f];
	c[!f]=fa;
	fa=c[!f]->fa;
	if(c[!f]->fa->c[1]==c[!f])
		c[!f]->fa->c[1]=this;
	else if(c[!f]->fa->c[0]==c[!f])
		c[!f]->fa->c[0]=this;
	c[!f]->fa=this;
	c[!f]->c[f]->fa=c[!f];
	c[!f]->pushup();
}

inline void node::pushup()
{
	ma=val;
	if(c[0]!=null)repr(ma,c[0]->ma);
	if(c[1]!=null)repr(ma,c[1]->ma);
}

inline void init(node *x,int v)
{
	x->val=v,x->c[0]=null,x->c[1]=null,x->fa=null;
}

inline void splay(node *a)
{
	a->pushdown();
	while(a->fa->c[0]==a||a->fa->c[1]==a)
		a->rotate(a==a->fa->c[1]);
	a->pushup();
}

inline void access(node *a)
{
	node *x=null;
	while(a!=null)
	{
		splay(a);
		a->c[1]=x;
		a->pushup();
		x=a,a=a->fa;
	}
}

inline void movetoroot(node *x)
{
	access(x);
	splay(x);
	x->rev=!x->rev;
}

inline void link(node *x,node *y)
{
	movetoroot(x);
	x->fa=y;
}

inline void cut(node *x,node *y)
{
	movetoroot(x);
	access(y);
	splay(y);
	x->fa=null;
	y->c[0]=null;
	y->pushup();
}

inline void split(node *x,node *y)
{
	movetoroot(x),access(y),splay(y);
}

inline node* findroot(node *x)
{
	while(x->fa!=null)
		x=x->fa;
	return x;
}

int main()
{
	int n,m,lstans=0,opt,x,y;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		init(s+i,0);
	for(int i=1,ec=0;i<=m;i++)
	{
		scanf("%d%d%d",&opt,&x,&y);
		x^=lstans,y^=lstans;
		if(opt==0)
		{
			ec++;
			if(findroot(s+x)!=findroot(s+y))
			{
				init(s+n+ec,ec);
				link(s+x,s+n+ec);
				link(s+y,s+n+ec);
			}
		}
		else
		{
			split(s+x,s+y);
			if(findroot(s+x)==s+y)
				lstans=s[y].ma;
			else
				lstans=0;
			printf("%d\n",lstans);
		}
	}
}
```

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

admin — Wed, 09 Nov 2016 12:55:00 +0800

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

mcfx's blog - 2016年11月

BZOJ 3113: Toy

BZOJ 4722: 由乃

BZOJ 3196: Tyvj 1730 二逼平衡树

BZOJ 3343: 教主的魔法 分块

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

BZOJ 4668: 冷战 LCT

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

BZOJ 3343: 教主的魔法分块