题目链接：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 树状数组+模拟,布布扣,bubuko.com
Codeforces 216D Spider's Web 树状数组+模拟
原文：http://blog.csdn.net/qq574857122/article/details/32942489