Description
Yaroslav has n points that lie on the axis. The coordinate of the first point is , the coordinate of the second point is , ..., the coordinate of the n-th point is — . Now Yaroslav wants to execute queries, each of them is of one of the two following types:
Move the -th point from position to position . 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 . In other words, you should count the sum of:
Help Yaroslav.
- time limit per test: 5 seconds
- memory limit per test: 256 megabytes
- input: standard input
- output: standard output
Input
The first line contains integer — the number of points (). The second line contains distinct integers — the coordinates of points ().
The third line contains integer — the number of queries (). The next lines contain the queries. The -th line first contains integer () — the query type. If , then it is followed by two integers and (). If , then it is followed by two integers and ().
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
题意:一维数轴上有 个点,每个点有坐标 ,现在对这个数轴上的点有两种操作:
- 改变某个坐标 ,将其增加 (每次操作 d 不同):
- 查询 区间内的 ,也就是两两点对距离之和。
Analysis
又双叒叕是线段树。
可以写个单点修改区间查询的线段树。首先由于数据规模过大,需要离散化,把操作离线下来,把所有可能出现的值(包括初始、修改和查询)全都离散。现在我们可以对于这个一维数轴建一棵线段树,对于每个点如果有则值为 1,否则为 0。那么对于每个区间(线段树的每个节点),需要存储以下三个信息:
- :这个区间中所有点坐标之和;
- :这个区间中的 ;
所以合并的时候(假设 ls 是左儿子,rs 是右儿子):
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;
numto[maxn*],sx[maxn];
{
x,y,z;
}zero_sts=(sts){,,};
SegmentTree{
tree[maxn*],sum[maxn*],num[maxn*];
{
(x==tl && tl==tr){
sum[p]+=delta*numto[x];
num[p]+=delta;
;
}
(x<=mid ) (x,delta,tl,mid,ls);
(mid<=x) (x,delta,mid,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];
}
{
(sl<=tl && tr<=sr){
(sts){sum[p],tree[p],num[p]};
}
sts ret1=zero_sts,ret2=zero_sts;
(sl<=mid ) ret1=(sl,sr,tl,mid,ls);
(mid<=sr) ret2=(sl,sr,mid,tr,rs);
sts ret=(sts){retx+retx, rety+rety+retz*retx-retz*retx, retz+retz};
ret;
}
}
{
x,y,z;
}opts[maxn];
{
n=();
vector<> vec;vec.();
( i=;i<=n;i++) numto[i]=sx[i]=(),vec.(numto[i]);
m=();
( i=;i<=m;i++){
opts[i].x=(),opts[i].y=(),opts[i].z=();
(opts[i].x==) numto[opts[i].y]+=opts[i].z,vec.(numto[opts[i].y]);
vec.(opts[i].y),vec.(opts[i].z);
}
(vec.(),vec.());(vec.(),vec.()); N=vec.();
( i=;i<=N;i++) numto[i]=vec[i],to[numto[i]]=i;
( i=;i<=n;i++) SegmentTree::(to[sx[i]],,,N,);
( i=;i<=m;i++){
(opts[i].x==){
SegmentTree::(to[sx[opts[i].y]],,,N,);
sx[opts[i].y]+=opts[i].z;
SegmentTree::(to[sx[opts[i].y]],,,N,);
} {
sts ans=SegmentTree::(to[opts[i].y],to[opts[i].z],,N,);
(,ans.y);
}
}
;
}