P7602 [THUPC2021] 视频倍增期

· · 题解

2021/9/30 UPD: 感谢 \text{\color{black}{s}\color{red}{yksykCCC}} 指出本题解中的一处错误。

提供一个从dmy老师那里嫖来的单 \log 做法，截至本题解发布时为最优解。

我们在写有区间操作的数据结构题时，一般以时间（即操作的先后顺序）为第一维，维护以横坐标为第二维的相关数据。在允许离线的题目上，有这样一种常用做法：以横坐标为第一维，维护以时间为第二维的相关数据。

回到本题，我们维护一个树状数组，若第 i 个操作为修改操作，则在 l_i 处记录“在树状数组的第 i 个位置加上 x_i”，在 r_i+1 处记录“在树状数组的第 i 个位置减去 x_i”。然后我们从 1 到 n 枚举横坐标，对于每个询问，先将当前处时间小于它的操作加到树状数组中，然后查询树状数组中第一个前缀和 \ge \lceil\frac{sum}{2}\rceil 的下标即可，其中 sum 表示当前的总和。可以通过树状数组上二分的黑科技做到单 \log。

（顺带一提 IOI2021D1T1 也用到了类似套路

实现细节可以看代码：

#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=1e5+10;
#define lowbit(k) ((k)&(-k))
template<typename T>
struct BIT{
    T c[maxn];
    int mx_idx;
    inline void clear(){memset(c,0,sizeof(T)*(mx_idx+1));}
    inline void add(int k,T v){
        for(;k<=mx_idx;k+=lowbit(k))c[k]+=v;
    }
    inline T query(int k){
        T ret=0;
        for(;k;k^=lowbit(k))ret+=c[k];
        return ret;
    }
    inline T query(int l,int r){
        return query(r)-query(l-1);
    }
    inline int half(ll k){
        if(!k)return 0;
        ri now=0;
        ll tot=0;
        for(ri i=1<<16;i;i>>=1){
            ri nxt=now|i;
            if(nxt<=mx_idx&&tot+c[nxt]<k)now=nxt,tot+=c[nxt];
        }
        return now+1;
    }
};
BIT<ll>c;
int ans[maxn],cnt,m,n;
struct node{
    bool tp;
    int pos,val;
};
vector<node>q[maxn];
#define pb push_back
int main(){
    scanf("%d%d",&n,&m);
    c.mx_idx=m;
    for(ri i=1;i<=m;++i){
        ri op,x,y,z;
        scanf("%d%d",&op,&x);
        if(op)q[x].pb({op,i,++cnt});
        else{
            scanf("%d%d",&y,&z);
            q[x].pb({op,i,z});
            q[y+1].pb({op,i,-z});
        }
    }
    for(ri i=1;i<=n;++i)
        for(node j:q[i])
            if(j.tp){
                ans[j.val]=j.pos-c.half((c.query(j.pos)+1)>>1);
            }
            else{
                c.add(j.pos,j.val);
            }
    for(ri i=1;i<=cnt;++i)printf("%d\n",ans[i]);
    return 0;
}