Codeforce Educational Round 6

Codeforce Educational Round 6
A:答えはmax(abs(x 1-x 2)、abs(y 1-y 2)).
B:時計を1枚打てばいいです.
C:題意:1つのシーケンスをできるだけ多くのセグメントに分け、セグメントは2つ交差せず、各セグメントに1対の重み値が同じ数しかない.
欲張ればいい、hashの代わりにmapを使い、2つ見つけるたびにclear.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

D:題意:2つのシーケンスを与え、0-2の数を交換して、2つのシーケンスのすべての数の和の差の絶対値を最小にすることができる.
(シーケンス長さが2000以下)
交換0回が本来の和の差です.(o(n+m))
交換は一度にn*m列挙できます.(o(n*m))
このように考えて、1番目のシーケンスがxの2つの数を選択し、2番目のシーケンスがyの2つの数を選択すると、最終的な答えはabs(s 1-s 2-2*x+2*y)であり、答えを最小にするために、2*y-2*xはできるだけs 2-s 2に近づくので、1つのxを選択した後、s 1-s 2+2*yが2*xに最も近い2つの数を選択するのが優れており、単調性があることに気づいた.では、n^2+m^2はすべての組み合わせを求めて、それぞれ並べ替えて、キューを持って単調にスキャンすればいいのです.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define Int long long
using namespace std;
struct node{Int val;int x;int y;
};node f[5000010],g[5000010];
Int A[2010],B[2010],Ans,s1 = 0,s2 = 0;
int x1,x2,x3,x4,n,m,tot,cnt;
bool comp(const node &x,const node &y) {return x.val < y.val;}
bool comp2(const node &x,const node &y) {return x.val == y.val;}
void work1() {
	for(int i = 1;i <= n;i ++)
	    for(int j = 1;j <= m;j ++)
	    {
	    	Int x = abs(s1 - s2 - 2ll * A[i] + 2ll * B[j]);
	    	if(x < Ans)
	    	{
	    		Ans = x;
	    		x1 = i;
	    		x2 = j;
	    	}
	    }
}
void work2() {
	if(n < 2 || m < 2) return ;
	for(int i = 1;i <= n;i ++)
	    for(int j = i + 1;j <= n;j ++)
	    {
	    	f[ ++ tot].val = A[i] + A[j];
	    	f[tot].x = i;
	    	f[tot].y = j;
	    }
	for(int i = 1;i <= m;i ++)
	    for(int j = i + 1;j <= m;j ++)
	    {
	    	g[ ++ cnt].val = B[i] + B[j];
	    	g[cnt].x = i;
	    	g[cnt].y = j;
	    }
	sort(f + 1,f + tot + 1,comp);
	tot = unique(f + 1,f + tot + 1,comp2) - f - 1;
	sort(g + 1,g + cnt + 1,comp);
	cnt = unique(g + 1,g + cnt + 1,comp2) - g - 1;
	int head = 1;
	for(int i = 1;i <= tot;i ++)
	{
		Int x = (s1 - s2 + 2ll * g[head].val);
		Int y = (s1 - s2 + 2ll * g[head + 1].val);
		while(head < cnt && abs(y - 2ll * f[i].val) < abs(x - 2ll * f[i].val))
		{
			head ++;
			x = (s1 - s2 + 2ll * g[head].val);
			y = (s1 - s2 + 2ll * g[head + 1].val);
		}
		Int ret = abs(s1 - s2 - 2ll * f[i].val + 2ll * g[head].val);
		if(ret < Ans)
		{
			Ans = ret;
			x1 = f[i].x;
			x3 = f[i].y;
			x2 = g[head].x;
			x4 = g[head].y;
		}
	}
}
int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++)
	    cin>>A[i],s1 += A[i];
	scanf("%d",&m);
	for(int i = 1;i <= m;i ++)
	    cin>>B[i],s2 += B[i];
	Ans = abs(s1 - s2);
	work1();
	work2();
	if(x3 != 0) cout<

E:題意:1本の木で、点に色があり、サブツリーの色を覆うたびに、またはサブツリーの色の数を尋ねる.(色の種類数は60種類未満です.)
Clarisは色を無視して怖くなると言っていました....
60色がちょうどlonglongの範囲内にあると思いますので、セグメントツリーでバイナリ数を維持し、更新するたびに|演算でメンテナンスすればいいと思います.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define Int long long
using namespace std;
struct node{int to;int next;
};node bian[800010];
int in[400010],out[400010],first[400010],size = 0;
int F[1600010],tim = 0,c[400010],n,m,a,b,p,Ans,num[400010];
Int val[1600010];
void inser(int x,int y) {
	size ++;
	bian[size].to = y;
	bian[size].next = first[x];
	first[x] = size;
}
void dfs(int x,int Anc) {
	in[x] = out[x] = ++ tim;num[tim] = x;
	for(int u = first[x];u;u = bian[u].next)
	    if(bian[u].to != Anc)
	    {
	    	dfs(bian[u].to,x);
	    	out[x] = max(out[x],out[bian[u].to]);
	    }
}
void pushdown(int Now) {
	F[Now << 1] = F[Now << 1 | 1] = F[Now];
	val[Now << 1] = val[Now << 1 | 1] = (1ll << (F[Now] - 1));
	F[Now] = 0;
	return ;
}
void build(int Now,int l,int r) {
	if(l == r)
	{
		val[Now] = (1ll << (c[num[l]] - 1));
		return ;
	}
	int Mid = (l + r) >> 1;
	build(Now << 1,l,Mid);
	build(Now << 1 | 1,Mid + 1,r);
	val[Now] = val[Now << 1] | val[Now << 1 | 1];
}
void modify(int Now,int l,int r,int x,int y,int z) {
	if(l >= x && r <= y)
	{
		F[Now] = z;
		val[Now] = (1ll << (z - 1));
		return ;
	}
	if(F[Now] != 0) pushdown(Now);
	int Mid = (l + r) >> 1;
	if(x <= Mid) modify(Now << 1,l,Mid,x,y,z);
	if(y > Mid) modify(Now << 1 | 1,Mid + 1,r,x,y,z);
	val[Now] = val[Now << 1] | val[Now << 1 | 1];
}
Int Ask(int Now,int l,int r,int x,int y) {
	if(l >= x && r <= y) return val[Now];
	if(F[Now] != 0) pushdown(Now);
	int Mid = (l + r) >> 1;
	Int ret = 0;
	if(x <= Mid) ret |= Ask(Now << 1,l,Mid,x,y);
	if(y > Mid) ret |= Ask(Now << 1 | 1,Mid + 1,r,x,y);
	val[Now] = val[Now << 1] | val[Now << 1 | 1];
	return ret;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i ++) scanf("%d",&c[i]);
	for(int i = 1;i < n;i ++)
	{
		scanf("%d%d",&a,&b);
		inser(a,b);
		inser(b,a);
	}
	dfs(1,1);
	build(1,1,n);
	for(int i = 1;i <= m;i ++)
	{
		scanf("%d",&p);
		if(p == 1)
		{
			scanf("%d%d",&a,&b);
			modify(1,1,n,in[a],out[a],b);
		}
		else 
		{
			Ans = 0;
			scanf("%d",&a);
			Int w = Ask(1,1,n,in[a],out[a]);
			while(w > 0)
			{
				if(w % 2 == 1) Ans ++;
			    w >>= 1;
			}
			printf("%d
",Ans);
		}
	}
	return 0;
}