P5103 [JOI 2016 Final] 断层 题解

· · 题解

提高 T1 难度 远古 JOI 题。这东西能评黑？？？

干什么

有两个长度为 n 个序列 (x_1,x_2,\dots,x_n),(y_1,y_2,\dots,y_n)，初始化 x_i=y_i=i。有 q 次操作，每次给你三个数 X,D,L，若 D=1 将所有满足 x_i\le X 的 i 的 y_i 减 2L，若 D=2 则将所有满足 y_i> X 的 i 的 x_i 加 2L，求出最终的 x,y 序列。

怎么做

发现 x,y 两个序列任意时刻都是单调递增的，两种操作分别是前缀减和后缀加，二分出修改的区间然后树状数组维护即可，时间复杂度 O(q\log^2 n)。

代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 200003
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
struct node{
    ll x,d,l;
}a[mxn];
int n,q;
struct tree{
    ll c[mxn];
    void add(int x,int y){for(;x<=n;x+=x&-x)c[x]+=y;}
    ll ask(int x){
        ll s=0;
        for(;x;x-=x&-x)s+=c[x];
        return s;
    }
}c1,c2;
signed main(){
    scanf("%d%d",&n,&q);
    rep(i,1,q)scanf("%lld%lld%lld",&a[i].x,&a[i].d,&a[i].l),a[i].l<<=1;
    rep(i,1,n)c1.add(i,1),c2.add(i,1);
    drep(j,q,1){
        if(a[j].d==1){
            int l=1,r=n;
            while(l<r){
                int mid=(l+r+1)>>1;
                if(c1.ask(mid)<=a[j].x)l=mid;
                else r=mid-1;
            }
            if(c1.ask(l)<=a[j].x)c2.add(1,-a[j].l),c2.add(l+1,a[j].l);
        }else{
            int l=1,r=n;
            while(l<r){
                int mid=(l+r)>>1;
                if(c2.ask(mid)>a[j].x)r=mid;
                else l=mid+1;
            }
            if(c2.ask(l)>a[j].x)c1.add(l,a[j].l);
        }
    }
    rep(i,1,n)printf("%lld\n",(c1.ask(i)-c2.ask(i))>>1);
    return 0;
}