Codeforces 453E - Little Pony and Lord Tirek(二维线段树+ODT)
阅读原文时间:2023年07月09日阅读:2

Codeforces 题目传送门 & 洛谷题目传送门

一道难度 *3100 的 DS,而且被我自己搞出来了!

不过我终究还是技不如人,因为这是一个 \(n\log^2n\) + 大常数的辣鸡做法,几乎是卡着时空限制过去的……

首先注意到对于每个小马,在任意时刻它的法力值只有三种可能:

  • \(s_i+kr_i(k\in\mathbb{Z})\)
  • \(kr_i(k\in\mathbb{Z})\)
  • \(m_i\)

我们考虑对这三种情况一一分析,对于第一种情况这里的 \(k\) 只可能等于我们待查询的 \(t\),并且这种情况可能发生当且仅当 \(i\) 没有被清空过,并且 \(s_i+kr_i\le m_i\),第二个条件好办,我们如果设 \(a_i=\lfloor\dfrac{m_i-s_i}{r_i}\rfloor\)(如果 \(r_i=0\) 那么 \(a_i=\infty\)),那么 \(i\) 符合第二个条件当且仅当 \(a_i\ge t\),第一个条件虽然看起来棘手,但是我们可以维护一个 set 表示没有被清空过的集合,每次进行查询操作就将这个 set 中属于 \([l,r]\) 的元素全部删除,不难发现每个数最多被删除一次,因此复杂度是 \(n\log n\) 的。接下来问题就转化为如何维护这个值,显然它可以转化为 \(\sum\limits_{i=l}^r[a_i\ge t]s_i+t\sum\limits_{i=l}^r[a_i\ge t]r_i\),两部分结构类似,因此维护方法也类似,注意到这里涉及两维,\(i\in[l,r]\) 和 \(a_i\ge t\),那么该操作相当于查询矩形 \((l,a_i),(r,\infty)\) 中权值的和,这个离散化+建立二维线段树就可以搞定了,具体来说先将所有 \((i,a_i)\) 看作一个点并更新其在二维线段树上的权值,每次我们将一个数从 set 中删除就将对应的 \((i,a_i)\) 的贡献撤销掉,正确性显然。

搞清楚这个情况后,我们也可以顺带着把 \(i\) 没有被清空过的贡献都搞清楚,若 \(i\) 没有被清空过,可以分两种情况,\(a_i\ge t\) 那么贡献为 \(s_i+tr_i\),这个刚刚已经探究过了,\(a_i<t\) 那么贡献为 \(m_i\),不难发现这个也可以写成矩形和的形式,同样二维线段树维护即可,这里就不再赘述了。

\(i\) 没有被清空过的情况搞清楚了,接下来考虑 \(i\) 被清空过的情况,显然对于一个被清空过的 \(i\) 它都有一个上次被清空的时间 \(T_i\),在这 \(t-T_i\) 分钟内它的法力值最多可以上涨 \(r_i(t-T_i)\),那么它的贡献就是 \(\min(m_i,r_i(t-T_i))\),还是按照之前的套路,记 \(b_i=\lfloor\dfrac{m_i}{r_i}\rfloor\),还是分两种情况,若 \(b_i\ge t-T_i\),那么贡献为 \(r_i(t-T_i)\),否则贡献为 \(m_i\),这样还是不好做,因为这里的 \(T_i\) 都是互不相同的,无法直接维护。不过不难发现一个性质,那就是任意时刻 \(T_i\) 都是成段分布的,也就是说相同的 \(T_i\) 都是一段一段的,我们记三元组 \((l,r,t)\) 表示 \(\forall i\in[l,r],T_i=t\),我们考虑开一个 set 维护所有三元组并对每个三元组计算贡献——这个就可以按照上面的套路二维线段树了,相信如果理解了前面的部分那这边应该的相当容易的。我们还可以发现所有计算过贡献的三元组 \((l',r',t')\) 必定满足 \(l\le l'\le r'\le r\),这样的三元组在查询过后都会从 set 中删除,标准的 ODT 模型,按照 P4690 [Ynoi2016] 镜中的昆虫 的套路 维护即可。

时间复杂度 \(n\log^2n\),由于要维护五个二维线段树,常数巨大,但还好卡过去了(((

最后说一句,wtm 不是 sb,又拿未去重的数组离散化,话说恰好一年前的今天也犯过这个错误来着的?

const int MAXN=1e5;
const int MAXP=MAXN*20;
const int INF=0x3f3f3f3f;
int n,s[MAXN+5],r[MAXN+5],mx[MAXN+5],lim1[MAXN+5],lim2[MAXN+5];
int key1[MAXN+5],key2[MAXN+5],uni1[MAXN+5],uni2[MAXN+5],num1=0,num2=0;
struct seg2d{
    struct node{int ch[2];ll sum;} s[MAXP+5];
    int rt[MAXN+5],ncnt;
    seg2d(){ncnt=0;memset(rt,0,sizeof(rt));}
    void add_in(int &k,int l,int r,int x,int v){
        if(!k) k=++ncnt;s[k].sum+=v;
        if(l==r) return;int mid=l+r>>1;
        if(x<=mid) add_in(s[k].ch[0],l,mid,x,v);
        else add_in(s[k].ch[1],mid+1,r,x,v);
    }
    ll query_in(int k,int l,int r,int ql,int qr){
        if(ql>qr||!k) return 0;int mid=l+r>>1;
        if(ql<=l&&r<=qr) return s[k].sum;
        if(qr<=mid) return query_in(s[k].ch[0],l,mid,ql,qr);
        else if(ql>mid) return query_in(s[k].ch[1],mid+1,r,ql,qr);
        else return query_in(s[k].ch[0],l,mid,ql,mid)+query_in(s[k].ch[1],mid+1,r,mid+1,qr);
    }
    void add_out(int x,int p,int v){
        for(int i=x;i<=n;i+=(i&(-i))) add_in(rt[i],1,max(num1,num2),p,v);
    }
    ll query_out(int x,int l,int r){
        ll ret=0;
        for(int i=x;i;i&=(i-1)) ret+=query_in(rt[i],1,max(num1,num2),l,r);
        return ret;
    }
    ll query(int l1,int r1,int l2,int r2){return query_out(r1,l2,r2)-query_out(l1-1,l2,r2);}
} t_s,t_r,t_m,T_r,T_m;
set<int> fst;
struct event{
    int l,r,t;
    event(int _l=0,int _r=0,int _t=0):l(_l),r(_r),t(_t){}
    bool operator <(const event &rhs) const{return l<rhs.l;}
};
set<event> st;
void split(int x){
    if(st.empty()) return;
    set<event>::iterator it=st.lower_bound(event(x+1,0,0));
    if(it==st.begin()) return;
    --it;event val=*it;if(val.r<=x) return;
    st.erase(st.find(val));
    st.insert(event(val.l,x,val.t));
    st.insert(event(x+1,val.r,val.t));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&s[i],&mx[i],&r[i]);
    for(int i=1;i<=n;i++){
        if(r[i]){
            lim1[i]=mx[i]/r[i];
            lim2[i]=(mx[i]-s[i])/r[i];
        } else lim1[i]=lim2[i]=INF;
    }
    for(int i=1;i<=n;i++) key1[i]=lim1[i],key2[i]=lim2[i];
    sort(key1+1,key1+n+1);sort(key2+1,key2+n+1);key1[0]=-INF;key2[0]=-INF;
    for(int i=1;i<=n;i++) if(key1[i-1]!=key1[i]) uni1[++num1]=key1[i];
    for(int i=1;i<=n;i++) if(key2[i-1]!=key2[i]) uni2[++num2]=key2[i];
    for(int i=1;i<=n;i++){
        lim1[i]=lower_bound(uni1+1,uni1+num1+1,lim1[i])-uni1;//remember to unique
        lim2[i]=lower_bound(uni2+1,uni2+num2+1,lim2[i])-uni2;
//        printf("%d %d\n",lim1[i],lim2[i]);
    }
    for(int i=1;i<=n;i++) fst.insert(i);
    for(int i=1;i<=n;i++){
        t_s.add_out(i,lim2[i],s[i]);
        t_r.add_out(i,lim2[i],r[i]);
        t_m.add_out(i,lim2[i],mx[i]);
    } int qu;scanf("%d",&qu);
    while(qu--){
        int t,L,R;scanf("%d%d%d",&t,&L,&R);
        int pos=lower_bound(uni2+1,uni2+num2+1,t)-uni2;
        ll sums=t_s.query(L,R,pos,num2);
        ll sumr=t_r.query(L,R,pos,num2);
        ll summ=t_m.query(L,R,1,pos-1);
//        printf("%d %lld %lld %lld\n",pos,sums,sumr,summ);
//        printf("%lld\n",summ+sums+sumr*t);
        ll sum=summ+sums+sumr*t;
        if(L!=1) split(L-1);split(R);
        while(1){
            set<event>::iterator it=st.lower_bound(event(L,0,0));
            if(it==st.end()||(it->l)>R) break;event val=*it;
            int pp=lower_bound(uni1+1,uni1+num1+1,t-val.t)-uni1;
            ll ssumr=T_r.query(val.l,val.r,pp,num1);
            ll ssumm=T_m.query(val.l,val.r,1,pp-1);
//            printf("%d %d %d %d\n",val.l,val.r,t-val.t,pp);
//            printf("%lld %lld\n",ssumr,ssumm);
            sum+=ssumm+ssumr*(t-val.t);st.erase(st.find(val));
        } st.insert(event(L,R,t));
        while(1){
            set<int>::iterator it=fst.lower_bound(L);
            if(it==fst.end()||(*it)>R) break;
            int x=(*it);
            t_s.add_out(x,lim2[x],-s[x]);
            t_r.add_out(x,lim2[x],-r[x]);
            t_m.add_out(x,lim2[x],-mx[x]);
            T_r.add_out(x,lim1[x],r[x]);
            T_m.add_out(x,lim1[x],mx[x]);
            fst.erase(fst.find(x));
        } printf("%lld\n",sum);
    }
    return 0;
}
/*
10
0 4 2
0 3 0
0 96 7
0 25 9
0 90 4
0 93 5
0 87 3
0 58 3
0 65 8
0 30 0
10
3 3 4
10 1 7
11 8 9
19 4 9
28 3 10
33 5 10
38 4 5
45 5 7
48 5 9
58 1 4
*/