Codeforces 216D Spider's Web 树状数组+模拟

题目链接：http://codeforces.com/problemset/problem/216/D

题意：

对于一个梯形区域，如果梯形左边的点数！=梯形右边的点数，那么这个梯形为红色，否则为绿色，

问：

给定的蜘蛛网中有多少个红色。

2个树状数组维护2个线段。然后暴力模拟一下，因为点数很多但需要用到的线段树只有3条，所以类似滚动数组的思想优化内存。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define N 10010
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define ll int
int maxn;
struct hehe{
	int c[100505];
	void init(){memset(c, 0, sizeof c);}
	inline int Lowbit(int x){return x&(-x);}  
	void change(int i, int x)//i点增量为x  
	{  
		while(i <= maxn)  
		{  
			c[i] += x;  
			i += Lowbit(i);  
		}  
	}  
	int sum(int x){//区间求和 [1,x]  
		int ans = 0;  
		for(int i = x; i >= 1; i -= Lowbit(i))  
			ans += c[i];  
		return ans;  
	}  
}tree[2];
int ans;
vector<int>l,r,o;
void work(){
	if(o.size()<=1)return;
	tree[0].init(); tree[1].init();
	for(int i = 0; i < l.size(); i++)
		tree[0].change(l[i],1);
	for(int i = 0; i < r.size(); i++)
		tree[1].change(r[i],1);
	
	int L = o[0];
	for(int i = 1; i < o.size(); i++){
		int R = o[i];
		if(L+1<=R-1){
			int Z = tree[0].sum(R-1)-tree[0].sum(L);
			int Y = tree[1].sum(R-1)-tree[1].sum(L);
			ans += (Z!=Y);
		}
		L = R;
	}
}
vector<int>a,tmp1, red, tmp2, tmpend;
void Red(){
	red.clear();
	int HHH,EEE; scanf("%d",&HHH);
	while(HHH--){scanf("%d",&EEE);red.push_back(EEE);}
	sort(red.begin(),red.end());
}
int n;
int main(){
	int i,j,num;
	maxn = 100010;
	while(~scanf("%d",&n)){
		ans = 0;
		l.clear(); r.clear(); tmp1.clear(); a.clear();
		tmp2.clear(); tmpend.clear();
		Red();
		l = tmp1 = red;
		Red();
		tmp2 = o = red;
		for(i = 3; i <= n; i++){
			Red();
			r = red;
			if(i==n)tmpend = red;
			work();
			l = o;
			o = r;
		}
		r = tmp1;
		work();

		l = tmpend;
		o = tmp1;
		r = tmp2;
		work();
		cout<<ans<<endl;
	}
	return 0;
}
/*
3
2 1 3
3 1 3 2
3 1 3 2



ans:
0
2





*/
/*
ll n,m,k;
ll a[N];
ll gcd(ll x,ll y){
if(x>y)swap(x,y);
while(x){
y%=x;
swap(x,y);
}
return y;
}
int main(){
ll i, j, u, v, que;
while(cin>>n>>m>>k){
for(i = 1; i <= n; i++)cin>>a[i];
ll _gcd = a[1];
for(i = 2; i <= n; i++)_gcd = gcd(_gcd,a[i]);
for(i = 1; i <= n; i++)a[i]/=_gcd;


}
return 0;
}
/*

*/

Codeforces 216D Spider's Web 树状数组+模拟,古老的榕树,5-wow.com