[IOI 2007] 돛

[IOI 2007] 돛
선분 트 리 또는 기타 데이터 구조 유지 욕심
문 제 를 분석 하려 면 깃발 을 합 리 적 으로 배치 하여 각 줄 의 깃발 개 수 를 평균 적 으로 해 야 합 니 다. 정 답 은 \ (\ sum {cnct [i] * (cnt [i] - 1) / 2} \) 입 니 다.
높이 가 낮은 깃대 가 깃발 을 놓 는 것 이 비교적 원활 하지 않다 (?) 는 것 을 고려 하여 우 리 는 먼저 비교적 낮은 깃대 를 놓 고, 고 르 지 않 은 것 은 비교적 높 은 깃대 로 보충 하도록 한다.
\ (h, k \) 에 대해 우 리 는 \ (h \) 에 따라 순 서 를 늘 리 고 문 제 는 \ (1 - h \) 에서 가장 작은 \ (k \) 개 위치 에 깃발 을 놓 는 것 으로 바 뀌 었 다.
가장 작은 위 치 를 폭력 적 으로 찾 을 수 는 없 지만, 우 리 는 처리 하 는 과정 에서 깃발 의 개 수 를 \ (1 - h \) 에서 점차 줄 일 수 있 습 니 다. 그러면 가장 작은 k 개 를 고려 하지 않 아 도 됩 니 다.
어떻게 체감 을 보증 합 니까?
매번 조작 할 때마다 \ (1 \) 만 바 뀌 기 때문에 우 리 는 먼저 \ (h - k + 1, h \) 에서 가장 작은 값 \ (x \) 과 이 값 이 나타 나 는 가장 왼쪽, 오른쪽 위 치 를 찾 습 니 다 \ (L, R \)
\ ([R + 1, h], [L, L + (k - (h - R) + 1] \) 이 두 부분 을 + 1 하면 단조 성 을 보장 합 니 다.

#include
using namespace std;
 
#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)
 
inline void cmax(int &a,int b){ ((ab)&&(a=b));} 
 
 
char IO;
int rd(){
    int s=0,f=0;
    while(!isdigit(IO=getchar())) f|=(IO=='-');
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}
 
const int N=1e5+10;
const int R=1e5;
 
int n;
struct Node{
    int h,k;
    bool operator < (const Node __) const {
        return h<__.h a="" int="" s="" void="" down="" p="" if="" return="" t="" upd="" l="" r="" ql="" qr="" x="">qr) return;
    if(ql==l&&qr==r) {
        t[p]+=x;
        s[p]+=x;
        return;
    }
    Down(p);
    int mid=(l+r)>>1;
    if(qr<=mid) Upd(p<<1,l,mid,ql,qr,x);
    else if(ql>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
    else Upd(p<<1,l,mid,ql,mid,x),Upd(p<<1|1,mid+1,r,mid+1,qr,x);
    s[p]=max(s[p<<1],s[p<<1|1]);
}
 
int Que1(int p,int l,int r,int x) {
    do {
        int mid=(l+r)>>1;
        Down(p);
        x<=mid?(p=p<<1,r=mid):(p=p<<1|1,l=mid+1);
    } while(l!=r);
    return s[p];
}
 
int Que2(int p,int l,int r,int x) {
    do {
        int mid=(l+r)>>1;
        Down(p);
        if(s[p<<1|1]>x) p=p<<1|1,l=mid+1;
        else p=p<<1,r=mid;
    } while(l!=r);
    return s[p]<=x?1:l+1;
}
 
 
int main(){
    rep(i,1,n=rd()) A[i].h=rd(),A[i].k=rd();
    sort(A+1,A+n+1);
    rep(i,1,n) {
        int x=Que1(1,1,R,A[i].h-A[i].k+1);
        int l=Que2(1,1,R,x-1),r=Que2(1,1,R,x);
        Upd(1,1,R,l,A[i].h,1);
        Upd(1,1,R,r,r+A[i].k-max(0,(A[i].h-l+1))-1,1);
    }
    ll ans=0;
    rep(i,1,R) {
        int x=Que1(1,1,R,i);
        ans+=1ll*x*(x-1)/2;
    }
    printf("%lld
",ans);
}