ZOJ@3453 题目连接题意：有N个敌人，排成一排编号为1~n；对于敌人i有一个初始value[i]；对于敌人i，其朋友范围区间[Li,Ri]，i可能在[Li,Ri]区间内。你每次从右边发射子弹，第i颗子弹值为Ki，打中第一个value值大于或等于Ki的敌人，该敌人value值变为1，其朋友范围内的敌人value值均增加1；但是，如果没有敌人的value值大于或者等于Ki，则所有敌人value值增加1。求最后敌人中最高的value值。
解法：线段树，每个节点设置一个max、add元素，max表示该区间上的最大值，add表示该区间增加的值；实现（1）区间段元素+1操作，即对应的区间add+1；（2）对于对某个value值置1，即可将max=-覆盖该点的所有区间add累加值+1；（3）查找大于或等于K的最右元素。
// 2385696 2011-01-14 20:30:00 Accepted 3453 C++ 430 6040 redsea
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 100005;
int fr[maxn], fl[maxn], value[maxn];
struct node{
int cr,cl;
int r,l;
int max, add;
}st[maxn*2];
int len;
int build(int l,int r, int root)
{
if(l==r){
st[root].cr = st[root].cl = -1;
st[root].r = r;
st[root].l = l;
st[root].max = value[l];
st[root].add = 0;
return value[l];
}else{
int mid = (l+r)/2;
st[root].r = r;
st[root].l = l;
len++;
int ll = len;
st[root].cl = ll;
int m1 = build(l,mid, ll);
len++;
int rr = len;
st[root].cr = rr;
int m2 = build(mid+1,r,rr);
st[root].add = 0;
st[root].max = (m1<m2?m2:m1);
return st[root].max;
}
}
int add(int l, int r, int root)
{
if(root < 0)return -1000000000;
else if(st[root].l > r || st[root].r < l){
return -1000000000;
}
else if(l <= st[root].l && r >= st[root].r){
st[root].add++;
st[root].max++;
return st[root].max;
}else{
int m1 = add(l,r,st[root].cl);
int m2 = add(l,r,st[root].cr);
if(m1<m2)m1=m2;
if(st[root].max < m1+st[root].add)st[root].max = m1+st[root].add;
return st[root].max;
}
}
int findMax(int x, int root, int a)
{
if(st[root].r == st[root].l)
return st[root].l;
else{
int l = st[root].cl;
int r = st[root].cr;
if(st[r].max + a+st[root].add >= x)
return findMax(x,r,a+st[root].add);
else
return findMax(x,l,a+st[root].add);
}
}
int setToOne(int w, int root, int a)
{
if(st[root].l == st[root].r)
{
st[root].add = 0;
st[root].max = -a + 1;
return st[root].max;
}else{
int l = st[root].cl;
int r = st[root].cr;
if(st[l].l <= w && st[l].r >= w){
int m1 =setToOne(w,l,a+st[root].add);
int m2 =st[r].max;
st[root].max = (m1<m2?m2:m1)+st[root].add;
return st[root].max;
}else{
int m1 = setToOne(w,r,a+st[root].add);
int m2 = st[l].max;
st[root].max = (m1<m2?m2:m1)+st[root].add;
return st[root].max;
}
}
}
int main()
{
int n, m, x;
while(scanf("%d",&n)!=EOF)
{
for(int i = 1; i <= n; i++){
scanf("%d%d%d",value+i,fl+i,fr+i);
}
len = 0;
build(1,n,0);
scanf("%d",&m);
while(m--)
{
scanf("%d",&x);
if(st[0].max < x){
add(1,n,0);
}
else{
int index = findMax(x,0,0);
setToOne(index,0,0);
add(fl[index],fr[index],0);
}
}
printf("%d\n",st[0].max);
}
return 0;
}