题解：P12762 [POI 2018 R2] 电信中继站 Transceivers

二阶堂希罗 · 2026-06-08 13:16:08 · 题解

没啥意思的题，大题思路是差分+线段树。

我们可以把一个电线杆的贡献拆成两个等差数列，考虑如何使用线段树维护等差数列。

等差数列我们维护两个标记：基础值 add 和公差 d 和一个线段树区间总和 sum，这样 l 到 r 区间的第 k 个数标记就加上了 add+(k-1)\times d。

我们数形结合一下：

上图是标记下放的过程，显然对于 l,r 区间标记下放，左区间标记仍为 add,d，而右区间变为 add+(mid+1-l)\times d,d。

在区间增加等差数列时，我们如上操作，不过需要考虑增加区间左端点 x 在 l 到 mid 之间的情况，此时左区间实际累加了 mid-x 个 d，此时右区间标记应修正为 add+(mid+1-\textrm{min}(x,l))\times d,d。

区间查询和普通线段树类似。

解决了维护等差数列这道题就做完了。

下附代码：

#include<iostream>
#include<cstdio>
#define int long long
#define PII pair<int,int>
using namespace std;
int n,m;
PII dx[300005];
struct node{
    int sum,add,d;
}tr[1200005];
void gettag(int k,int l,int r,int add,int d){
    tr[k].sum+=(r-l+1)*add+(r-l+1)*(r-l)/2*d;
    tr[k].add+=add;
    tr[k].d+=d;
}
void pushup(int k,int l,int r){
    tr[k].sum=tr[k*2].sum+tr[k*2+1].sum;
}
void pushdown(int k,int l,int r){
    int mid=(l+r)/2;
    gettag(k*2,l,mid,tr[k].add,tr[k].d);
    gettag(k*2+1,mid+1,r,tr[k].add+(mid-l+1)*tr[k].d,tr[k].d);
    tr[k].add=tr[k].d=0;
}
void update(int k,int l,int r,int x,int y,int add,int d){
    if(r<x||l>y) return;
    if(x<=l&&r<=y){
        gettag(k,l,r,add,d);
        return;
    }
    pushdown(k,l,r);
    int mid=(l+r)/2;
    update(k*2,l,mid,x,y,add,d);
    update(k*2+1,mid+1,r,x,y,add+max(0ll,(mid+1-max(x,l)))*d,d);
    pushup(k,l,r);
}
int query(int k,int l,int r,int x,int y){
    if(r<x||l>y) return 0;
    if(x<=l&&r<=y) return tr[k].sum;
    pushdown(k,l,r);
    int mid=(l+r)/2;
    return query(k*2,l,mid,x,y)+query(k*2+1,mid+1,r,x,y);
}
signed main(){
    cin>>n>>m;
    while(m--){
        char c;int x,y,z;cin>>c;
        if(c=='P'){
            cin>>x>>y>>z;dx[x]={y,z};
            int len=y/z;
            int l=max(1ll,x-len),r=min(n,x+len);
            update(1,1,n,l,x-1,y-(x-l)*z,z);
            update(1,1,n,x,r,y,-z);
        }else if(c=='U'){
            cin>>x;int y=dx[x].first,z=dx[x].second;
            int len=y/z;
            int l=max(1ll,x-len),r=min(n,x+len);
            update(1,1,n,l,x-1,-(y-(x-l)*z),-z);
            update(1,1,n,x,r,-y,z);
        }else{
            cin>>x>>y;
            cout<<(query(1,1,n,x,y))/(y-x+1)<<endl;
        }
    }
    return 0;
}