[USACO 2014 Gold] The Lazy Cow

作法：

題目要問的東西簡單來說就是，給定平面上的一些點，每個點有它的價值，現在可以用一個斜45度的正方形去蓋他，問蓋到的最大價值。首先一樣可以用座標變換把他變為和坐標軸平行的正方形，只要考慮 ( x , y ) -> ( x-y , x+y ) 即可，所以現在問題變回找的是一個和坐標軸平行的正方形( 並且他的邊長會變為 2*k )。考慮把所有點按照 x 坐標由小到大排序，這樣就可以用雙指標轉換為一維問題了。具體來說，我們對每個 y 坐標都記錄取他的話可以獲得多少的價值，那麼當算到第 i 個點的時候，把他的價值加到他的位置上，並且把所有過期的點( x 坐標和第 i 個點差太多的點 )的價值減掉，然後詢問現在如果使用長度為 2*k 的線段蓋下去，可以蓋到的最大價值為何。而要處理這個問題，只要注意到：每次在一個點加上一個值的時候，會影響到的所有長為 2*k 的區間是連續的，也就是如果我們改成把長 2*k 的區間都看成點，這個點的權重就是這個區間裡的價值總和，那麼每次修改就會變成修改一個區間的權重，查詢就是查詢所有數的最大值，於是就可以用線段樹做了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 , maxc=2000000+10 ;
 
int ST[maxc*4],tag[maxc*4] ;
 
void push(int id)
{
    if(!tag[id]) return ;
    ST[2*id]+=tag[id] ; tag[2*id]+=tag[id] ;
    ST[2*id+1]+=tag[id] ; tag[2*id+1]+=tag[id] ;
    tag[id]=0 ;
}
 
void modify(int l,int r,int L,int R,int id,int val)
{
    if(l==L && r==R) { ST[id]+=val ; tag[id]+=val ; return ; }
    push(id) ;
    int mid=(L+R)/2 ;
    if(r<=mid) modify(l,r,L,mid,2*id,val) ;
    else if(l>mid) modify(l,r,mid+1,R,2*id+1,val) ;
    else modify(l,mid,L,mid,2*id,val) ,
            modify(mid+1,r,mid+1,R,2*id+1,val) ;
    ST[id]=max(ST[2*id],ST[2*id+1]) ;
}
 
struct P
{
    int x,l,r,val ;
    bool operator < (const P &rhs) const
    {
        return x<rhs.x ;
    }
}p[maxn];
 
main()
{
    if(fopen("lazy.in","r"))
    {
        freopen("lazy.in","r",stdin) ;
        freopen("lazy.out","w",stdout) ;
    }
    int n,k ; scanf("%d%d",&n,&k) ;
    for(int i=1;i<=n;i++)
    {
        int x,y,val ; scanf("%d%d%d",&val,&x,&y) ;
        p[i]=(P){x-y,max(x+y-2*k,0),x+y,val} ;
    }
    sort(p+1,p+n+1) ;
    int ans=0 ;
    for(int i=1,j=1;i<=n;i++)
    {
        modify(p[i].l,p[i].r,0,maxc,1,p[i].val) ;
        while(p[j].x+2*k < p[i].x)
            modify(p[j].l,p[j].r,0,maxc,1,-p[j].val) , j++ ;
        ans=max(ans,ST[1]) ;
    }
    printf("%d\n",ans) ;
}