Reku
0%

最近的四道题

Posted on Edited on In Views: Valine:

http://codeforces.com/contest/380/problem/C

题目大意：给定一个括号序列，给出一个询问\(l\)和\(r\)，回答\(l\)到\(r\)这个范围内，最长的合法子序列是多长

经过观察，这个题目符合区间合并性。 \[w[Total].len=w[Left].len+w[Right].len+min(w[Left].open+w[Right].closed)\] \[w[Total].open=w[Left].open+w[Right].open-min(w[Left].open+w[Right].closed)\] \[w[Total].closed=w[Left].closed+w[Right].closed-min(w[Left].open+w[Right].closed)\] 这样就可以用线段树来维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
using namespace std;
struct node{
	int z,y,len;
};
char s[1000010];
int n,m;
node w[4000010];
void build(int o,int l,int r)
{
	if(l==r)
	{
		//cout<<l<<" "<<s[l]<<" "<<o<<endl;
		if(s[l]=='(') w[o].z=1;
		else w[o].y=1;
		w[o].len=0;
		return;
	}
	int m=(l+r)/2;
	node zz; node yy;
	build(o*2,l,m);
	zz=w[o*2];
	build(o*2+1,m+1,r);
	yy=w[o*2+1];
	w[o].len=w[o*2].len+w[o*2+1].len+min(w[o*2].z,w[o*2+1].y)*2;
	w[o].z=w[o*2].z+w[o*2+1].z-min(w[o*2].z,w[o*2+1].y);
	w[o].y=w[o*2].y+w[o*2+1].y-min(w[o*2].z,w[o*2+1].y);
}
node ans;
int a,b;
node query(int o,int L,int R)
{
	int M=L+(R-L)/2;
	node ans;
	if(a<=L&&R<=b)
	{
		//cout<<a<<" "<<b<<" "<<o<<" "<<w[o].z<<" "<<w[o].y<<" "<<w[o].len<<endl;
		return w[o];
	}
	node zz;
	node yy;
	ans.len=0;ans.z=0;ans.y=0;
	zz.len=0;zz.z=0;zz.y=0;
	yy.len=0;yy.z=0;yy.y=0;
	if(a<=M)
	{
		zz=query(o*2,L,M);
	}
	if(M<b)
	{
		yy=query(o*2+1,M+1,R);
	}
	ans.len=zz.len+yy.len+min(zz.z,yy.y)*2;
	ans.z=zz.z+yy.z-min(zz.z,yy.y);
	ans.y=zz.y+yy.y-min(zz.z,yy.y);
	return ans;
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	build(1,1,n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		ans=query(1,1,n);
		printf("%d\n",ans.len);
	}
	return 0;
}

http://codeforces.com/contest/383/problem/C

题目大意：对一个节点加一个值\(val\)，其每一个子节点都要减去值\(val\)，向下不断传导，直到没有子节点。给出修改和查询，输出查询的答案。

根据层数的奇偶性，对dfs序建立两个树状数组（或者线段树），因为dfs序的子树处于同一区间，所以就是区间修改，单点查询。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
class TreeDiv{
public:
	static const int SIZE=200010,BIAS=5;
	long long u[2][SIZE];
	void clear(){
		memset(u,0,sizeof(u));
	}
	void modify(int x,bool f,long long v){
		for(x+=BIAS;x<SIZE;x+=x&-x) u[f][x]+=v,u[!f][x]-=v;
	}
	long long getsum(int x,bool f){
		long long s=0;
		for(x+=BIAS;x;x-=x&-x) s+=u[f][x];
		return s;
	}
} tr;
int v[200010]={};
vector<int> e[200010];
int n,m;
int a,b,c;
int l[200010]={};
int r[200010]={};
bool flag[200010]={};
int deep;
void dfs(int pr,int x,bool f)
{
	l[x]=++deep;
	flag[x]=f;
	for(int i=0;i<e[x].size();i++)
	{
		if(e[x][i]!=pr)
		{
			dfs(x,e[x][i],!f);
		}
	}
	r[x]=deep;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&v[i]);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(0,1,0);
	tr.clear();
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		if(a==1)
		{
			scanf("%d",&c);
			tr.modify(l[b],flag[b],c);
			tr.modify(r[b]+1,flag[b],-c);
		}
		else
		{
			printf("%d\n",v[b]+tr.getsum(l[b],flag[b]));
		}
	}
	return 0;
}

http://codeforces.com/contest/414/problem/C 这题基本给定个一个归并的阶段。所以用归并排序求一下逆序数，然后翻转的话，就是整个层以及层以下都翻转（正序变成逆序，逆序变成正序），所以记录一下每一层的正序数、逆序数，暴力维护即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1100000]={};
int tmp[1100000]={};
int q;
long long v[22][3]={};
bool bj[22]={};
long long ff(int l,int r,int d)
{
	if(d==0) return 0;
	int ll,rr,mid=(l+r)/2;
	long long t,b,c;
	t=0,b=0,c=0;
	v[d][2]+=(c=ff(l,mid,d-1)+ff(mid+1,r,d-1));
	ll=l,rr=mid+1;
	for(int i=l;i<=r;i++)
	{
		if(ll>mid||(rr<=r&&a[rr]<a[ll]))
		{
			tmp[i]=a[rr++];
			t+=mid-ll+1;
		}
		else tmp[i]=a[ll++];
	}
	ll=l,rr=mid+1;
	for(int i=l;i<=r;i++)
	{
		if(rr>r||(ll<=mid&&a[ll]<a[rr]))
		{
			tmp[i]=a[ll++];
			b+=r-rr+1;
		}
		else tmp[i]=a[rr++];
	}
	for(int i=l;i<=r;i++) a[i]=tmp[i];
	v[d][0]+=t;
	v[d][1]+=b;
	v[d][2]+=t;
	return t+c;
}
int main()
{
	scanf("%d",&n);
	m=1<<n;
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&a[i]);
	}
	ff(1,m,n);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int x;
		scanf("%d",&x);
		for(int i=1;i<=n;i++)
		{
			if(i<=x) bj[i]=!bj[i];
			v[i][2]=v[i-1][2]+v[i][bj[i]];
		}
		printf("%I64d\n",v[n][2]);
	}
	return 0;
}

http://codeforces.com/contest/282/problem/E 用trie树进行贪心，第一次接触到这种东西

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[100010]={};
long long p[100010]={};
long long h[100010]={};
int tr[5000010][2]={};
int si=0;
void cha(long long p)
{
	bool e[50]={};
	for(int i=45;i>=0;i--)
	{
		long long o=1ll<<i;
		if(p&o)
		{
			e[i]=1;
		}
		else e[i]=0;
	}
	int t=0;
	for(int i=45;i>=0;i--)
	{
		if(tr[t][e[i]]==0)
		{
			si++;
			tr[t][e[i]]=si;
		}
		t=tr[t][e[i]];
	}
}
long long query(long long p)
{
	long long ans=0;
	int t=0;
	for(int i=45;i>=0;i--)
	{
		long long o=1ll<<i;
		if((p&o)&&tr[t][0])
		{
			//cout<<p<<" "<<o<<" "<<t<<" *****"<<endl;
			
			ans+=o;
			t=tr[t][0];
		}
		else if(tr[t][1]==0)
		{
			t=tr[t][0];
		}
		else if((p&o)==0)
		{
			//cout<<p<<" "<<o<<" "<<" _____"<<endl;
			ans+=o;
			t=tr[t][1];
		}
		else t=tr[t][1];
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%I64d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		p[i]=p[i-1]^a[i];
	}
	for(int i=n;i>=1;i--)
	{
		h[i]=h[i+1]^a[i];
	}
	long long ans=0;
	for(int i=1;i<=n+1;i++)
	{
		cha(p[i-1]);
		ans=max(ans,query(h[i]));
	}
	printf("%I64d\n",ans);
	return 0;
}