SkyWT / 博客 / CodeForces 295E - Yaroslav and Points 题解:又是线段树!

CodeForces 295E - Yaroslav and Points 题解:又是线段树!

2019 年 1 月 30 日 13:20


文章目录

Description

Yaroslav has n points that lie on the OxOx axis. The coordinate of the first point is x1x_1, the coordinate of the second point is x2x_2, ..., the coordinate of the n-th point is — xnx_n. Now Yaroslav wants to execute mm queries, each of them is of one of the two following types:

Move the pjp_j-th point from position xpjx_{p_j} to position xpj+djx_{p_j} + d_j. At that, it is guaranteed that after executing such query all coordinates of the points will be distinct.
Count the sum of distances between all pairs of points that lie on the segment [lj,rj](ljrj)[l_j, r_j] (l_j ≤ r_j). In other words, you should count the sum of: ljxpxqrj(xqxp)\displaystyle \sum_{l_j\leq x_p\leq x_q\leq r_j} (x_q-x_p)

Help Yaroslav.

Link

  • time limit per test: 5 seconds
  • memory limit per test: 256 megabytes
  • input: standard input
  • output: standard output

Input

The first line contains integer nn — the number of points (1n1051 ≤ n ≤ 10^5). The second line contains distinct integers x1,x2,,xnx_1, x_2, \dots , x_n — the coordinates of points (xi109|x_i| ≤ 10^9).

The third line contains integer mm — the number of queries (1m1051 ≤ m ≤ 10^5). The next mm lines contain the queries. The jj-th line first contains integer tjt_j (1tj21 ≤ t_j ≤ 2) — the query type. If tj=1t_j = 1, then it is followed by two integers pjp_j and djd_j (1pjn,dj10001 ≤ p_j ≤ n, |d_j| ≤ 1000). If tj=2t_j = 2, then it is followed by two integers ljl_j and rjr_j (109ljrj109- 10^9 ≤ l_j ≤ r_j ≤ 10^9).

It is guaranteed that at any moment all the points have distinct coordinates.

Output

For each type 2 query print the answer on a single line. Print the answers in the order, in which the queries follow in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams of the %I64d specifier.

Examples

Input

8
36 50 28 -75 40 -60 -95 -48
20
2 -61 29
1 5 -53
1 1 429
1 5 130
2 -101 -71
2 -69 53
1 1 404
1 5 518
2 -101 53
2 50 872
1 1 -207
2 -99 -40
1 7 -389
1 6 -171
1 2 464
1 7 -707
1 1 -730
1 1 560
2 635 644
1 7 -677

Output

176
20
406
1046
1638
156
0

Translation

题意:一维数轴上有 nn 个点,每个点有坐标 xix_i,现在对这个数轴上的点有两种操作:

  • 改变某个坐标 xix_i,将其增加 dd(每次操作 d 不同):
  • 查询 [Li,Ri][L_i,R_i] 区间内的 xi>xjxixj\sum_{x_i>x_j} x_i-x_j,也就是两两点对距离之和。

Analysis

又双叒叕是线段树。
可以写个单点修改区间查询的线段树。首先由于数据规模过大,需要离散化,把操作离线下来,把所有可能出现的值(包括初始、修改和查询)全都离散。现在我们可以对于这个一维数轴建一棵线段树,对于每个点如果有则值为 1,否则为 0。那么对于每个区间(线段树的每个节点),需要存储以下三个信息:

  • sumpsum_p:这个区间中所有点坐标之和;
  • treeptree_p:这个区间中的 xi>xjxixj\sum_{x_i>x_j} x_i-x_j
  • numpnum_p:这个区间中点的数量。
    接下来需要考虑如何合并。对于 sumpsum_pnumpnum_p 都可以子树对应直接相加,只有 treeptree_p 比较麻烦:

treep=xi>xjxixj=i=1nj=1nxii=1nj=1nxjtree_p=\sum_{x_i>x_j} x_i-x_j = \sum_{i=1}^n \sum_{j=1}^n x_i - \sum_{i=1}^n \sum_{j=1}^n x_j

所以合并的时候(假设 ls 是左儿子,rs 是右儿子):

treep=treels+treers+numlssumrs+numrssumlstree_p=tree_{ls}+tree_{rs}+num_{ls}\ast sum_{rs}+num_{rs}\ast sum_{ls}

Code

具体写起来要考虑一(很)点(多)细节 :new_moon_with_face: 。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;
#define int long long

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

const int maxn=2e5+5;
const pair<int,int> zero_pair=make_pair(0,0);
int n,m,N;
map<int,int> to;
int numto[maxn*2],sx[maxn];

#define ls ((p<<1))
#define rs ((p<<1)+1)
#define mid (((tr-tl)>>1)+tl)

struct sts{
    int x,y,z;
}zero_sts=(sts){0,0,0};

namespace SegmentTree{
    int tree[maxn*4],sum[maxn*4],num[maxn*4];

    inline void change(int x,int delta,int tl,int tr,int p){
        if (x==tl && tl==tr){
            sum[p]+=delta*numto[x];
            num[p]+=delta;
            return;
        }
        if (x<=mid  ) change(x,delta,tl,mid,ls);
        if (mid+1<=x) change(x,delta,mid+1,tr,rs);
        num[p]=num[ls]+num[rs];
        tree[p]=tree[ls]+tree[rs]+num[ls]*sum[rs]-num[rs]*sum[ls];
        sum[p]=sum[rs]+sum[ls];
        // printf("[%lld,%lld]: sum=%lld tree=%lld num=%lld\n",tl,tr,sum[p],tree[p],num[p]);
    }

    inline sts query(int sl,int sr,int tl,int tr,int p){
        if (sl<=tl && tr<=sr){
            // printf("tl=%lld tr=%lld sum=%lld tree=%lld num=%lld\n",tl,tr,sum[p],tree[p],num[p]);
            return (sts){sum[p],tree[p],num[p]};
        }
        sts ret1=zero_sts,ret2=zero_sts;
        if (sl<=mid  ) ret1=query(sl,sr,tl,mid,ls);
        if (mid+1<=sr) ret2=query(sl,sr,mid+1,tr,rs);
        sts ret=(sts){ret1.x+ret2.x,  ret1.y+ret2.y+ret1.z*ret2.x-ret2.z*ret1.x,  ret1.z+ret2.z};
        // printf("query (%lld %lld %lld %lld) : sum=%lld tree=%lld num=%lld\n",sl,sr,tl,tr,ret.x,ret.y,ret.z);;
        return ret;
    }
}

struct opt{
    int x,y,z;
}opts[maxn];

signed main(){
    n=read();
    vector<int> vec;vec.clear();
    for (int i=1;i<=n;i++) numto[i]=sx[i]=read(),vec.push_back(numto[i]);
    m=read();
    for (int i=1;i<=m;i++){
        opts[i].x=read(),opts[i].y=read(),opts[i].z=read();
        if (opts[i].x==1) numto[opts[i].y]+=opts[i].z,vec.push_back(numto[opts[i].y]);
        else vec.push_back(opts[i].y),vec.push_back(opts[i].z);
    }
    sort(vec.begin(),vec.end());unique(vec.begin(),vec.end()); N=vec.size();
    for (int i=1;i<=N;i++) numto[i]=vec[i-1],to[numto[i]]=i;//,cout<<i<<" --> "<<vec[i-1]<<endl;
    
    for (int i=1;i<=n;i++) SegmentTree::change(to[sx[i]],1,1,N,1);
    for (int i=1;i<=m;i++){
        if (opts[i].x==1){
            SegmentTree::change(to[sx[opts[i].y]],-1,1,N,1);
            sx[opts[i].y]+=opts[i].z;
            SegmentTree::change(to[sx[opts[i].y]],1,1,N,1);
        } else {
            sts ans=SegmentTree::query(to[opts[i].y],to[opts[i].z],1,N,1);
            printf("%lld\n",ans.y);
            // printf(" - %lld %lld %lld\n",ans.x,ans.y,ans.z);
        }
    }
    return 0;
}

暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。
(提交一次评论后,本提示将不再展示)