ZOJ@3453 題目連接題意：有N個(gè)敵人，排成一排編號(hào)為1~n；對(duì)于敵人i有一個(gè)初始value[i]；對(duì)于敵人i，其朋友范圍區(qū)間[Li,Ri]，i可能在[Li,Ri]區(qū)間內(nèi)。你每次從右邊發(fā)射子彈，第i顆子彈值為Ki，打中第一個(gè)value值大于或等于Ki的敵人，該敵人value值變?yōu)?，其朋友范圍內(nèi)的敵人value值均增加1；但是，如果沒(méi)有敵人的value值大于或者等于Ki，則所有敵人value值增加1。求最后敵人中最高的value值。
解法：線(xiàn)段樹(shù)，每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)max、add元素，max表示該區(qū)間上的最大值，add表示該區(qū)間增加的值；實(shí)現(xiàn)（1）區(qū)間段元素+1操作，即對(duì)應(yīng)的區(qū)間add+1；（2）對(duì)于對(duì)某個(gè)value值置1，即可將max=-覆蓋該點(diǎn)的所有區(qū)間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;
}