BZOJ1135: [POI2009]Lyz

題目大意：初始時滑冰俱樂部有1到n号的溜冰鞋各k雙。已知x号腳的人可以穿x到x+d的溜冰鞋。 有m次操作，每次包含兩個數ri，xi代表來了xi個ri号腳的人。xi為負，則代表走了這麼多人。 對于每次操作，輸出溜冰鞋是否足夠。

首先——

每次二分圖比對顯然是爆炸的

是以有這麼一個東西——

Hall定理：對于一個二分圖，設左邊有 n 個點，右邊有m個點，則左邊 n 個點能完全比對的充要條件是：對于1<=i<=n,左面任意i個點，都至少有i個右面的點與它相連

然後——

我們肯定不能一一枚舉所有的情況，這樣是 2人數 的

我們考慮隻挑一些有用的情況來算(也就是最差情況)，我們可以把所有的人想象成一個1~n的序列，每個位置存人數。假設我們選的不是腳的型号在連續的一段區間的人的話，分兩種情況讨論：

1.這些人對應的鞋的可選型号範圍是連續的。那麼我們不妨再選上中間沒有選到的人，這樣人數變多了，而範圍不會擴大，這樣選到的情況一定更劣的。是以我們無需計算最開始選擇的那種方案

2.不是連續的。那就更加好辦了，我們隻需要計算每段連續的部分就行了。這種情況合法當且僅當每段連續的區間都合法。

于是——

綜上所述我們隻需要判定每個連續的人形成的段是否滿足Hall定理即可

設我們選擇的是腳在 [l,r] 區間内的人， a[i] 代表型号為 i 的有多少人。

想滿足Hall定理，則對于任意的l,r我們必須滿足這個式子：

∑i=lra[i]<=(r−l+1+d)∗k

操作和詢問是 O(m) 的，大約是50W，每次枚舉端點+查詢+修改是 O(n2logn) 的，時間複雜度還是接受不了

于是我們把式子換一種形式寫出來

∑i=lr(a[i]−k)<=d∗k

d∗k 是一個定值，現在相當于詢問把每個 a[i]−k 之後查詢最大連續和并檢驗其是否小于等于 d∗k

那麼這件事情就可以用線段樹來維護了，需要支援單點修改，最開始的時候把所有的 a[i] 都設為 −k 就好了

#include<iostream>
#include<cstdio>
#define N 200010
using namespace std;
long long l[N<<],r[N<<],lm[N<<],rm[N<<],w[N<<],sum[N<<];
long long n,m,k,d;
void pup(long long x)
{
    lm[x]=max(lm[x<<],sum[x<<]+lm[x<<|]);
    rm[x]=max(rm[x<<|],sum[x<<|]+rm[x<<]);
    sum[x]=sum[x<<]+sum[x<<|];
    w[x]=max(w[x<<],max(w[x<<|],rm[x<<]+lm[x<<|]));
}
void build(long long now,long long ll,long long rr)
{
    l[now]=ll;r[now]=rr;
    if(ll==rr) {sum[now]=w[now]=-k;return;}
    long long mid=(ll+rr)>>;
    build(now<<,ll,mid);
    build(now<<|,mid+,rr);
    pup(now);
}
void change(long long now,long long x,long long v)
{
    if(l[now]==r[now])
    {
        w[now]+=v;sum[now]=w[now];
        if(w[now]>) lm[now]=rm[now]=w[now];
        else lm[now]=rm[now]=;
        return;
    }
    long long mid=(l[now]+r[now])>>;
    if(x<=mid) change(now<<,x,v);
    else change(now<<|,x,v);
    pup(now);
}
int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&k,&d);
    build(,,n);
    long long i,j,x,y;
    for(i=;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        change(,x,y);
        if(w[]>k*d) puts("NIE");
        else puts("TAK");
    }
}