权值线段树线段树与简单线段树的区别就像他的名字一样,他的叶子节点存的并不是数组的下表,而是数组中数的权值
此外,他的查询与普通线段树有所区别,画图即可理解
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int w[N],a[N];
int n;
struct node{
int l,r,sum;
}tr[N*8];
void build(int root,int l,int r){
tr[root]={l,r,0};
if(l == r) return;
int mid = l + r >> 1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
}
void pushup(int root){
tr[root].sum = tr[root<<1].sum + tr[root<<1|1].sum;
}
void change(int root,int pos,int val){
if(tr[root].l == pos && tr[root].r == pos){
tr[root].sum += val;
return;
}
int mid = tr[root].l + tr[root].r >> 1;
if(mid>=pos) change(root<<1,pos,val);
else change(root<<1|1,pos,val);
pushup(root);
}
int query(int root,int l,int r){
if(l > r) return 0;
if(tr[root].l == l && tr[root].r == r) return tr[root].sum;
int mid = tr[root].l + tr[root].r >> 1;
if(mid<l) return query(root<<1|1,l,r);
else{
if(r<=mid) return query(root<<1,l,r);
else return query(root<<1,l,mid) + query(root<<1|1,mid+1,r);
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>w[i],a[i] = w[i];
sort(w+1,w+n+1);
for(int i=1;i<=n;i++){
a[i] = lower_bound(w+1,w+n+1,a[i]) - w;
}
long long ans = 0;
build(1,1,n+1);
for(int i=1;i<=n;i++){
ans+=query(1,a[i]+1,n+1);
change(1,a[i],1);
}
cout<<ans<<endl;
return 0;
}
#include<bits/stdc++.h>
#define re read()
using namespace std;
const int MAXN=1e6+10;
int n,q,A[MAXN];
struct SEGTREE{
int sum;//sum 最大为10^6 无需long long(我第一次手残开了,然后爆了空间)
}tr[MAXN<<2];
int read(){//快读
#define gt getchar()
#define isdi(a) (a>='0'&&a<='9')
int x=0,sgn=1;char ch=gt;
for(;!isdi(ch);ch=gt)if(ch=='-')sgn=-1;
for(;isdi(ch);ch=gt)x=(x<<1)+(x<<3)+(ch^48);
return x*sgn;
}
void build(int k,int l,int r){ //建树
if(l==r){
tr[k].sum=A[l];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid); build(k<<1|1,mid+1,r);
tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
return;
}
void add(int k,int l,int r,int num){//加入元素
if(l==r){
if(l==num)tr[k].sum++;
return;
}
int mid=(l+r)>>1;
if(num>mid)add(k<<1|1,mid+1,r,num);
else add(k<<1,l,mid,num);
tr[k].sum++;
return;
}
void del(int k,int l,int r,int num){
//删除该区间内第num大的元素
if(l==r){
if(tr[k].sum)tr[k].sum--;
return;
}
if(num>tr[k].sum)return;
int mid=(l+r)>>1;
if(num>tr[k<<1].sum)del(k<<1|1,mid+1,r,num-tr[k<<1].sum);
//如果num大于左子树元素出现的总次数,则去右子树删第(num-左子树元素出现总次数)大的数
else if(num<=tr[k<<1].sum)del(k<<1,l,mid,num);
//否则去左子树删除第num大的数
else return;
tr[k].sum--;
//该区间内的次数减一
return;
}
int find(int k,int l,int r){//递归查找
if(l==r){
if(tr[k].sum)return l;
return 0;
}
int mid=(l+r)>>1;
if(tr[k<<1].sum)return find(k<<1,l,mid);
else return find(k<<1|1,mid+1,r);
return 0;
//根据题目,随便找一个就行了,找不到就输出0
}
int main (){
n=re;q=re;
for(int i=1;i<=n;i++){
int temp=re;
A[temp]++;
}
build(1,1,n);
for(int i=1;i<=q;i++){
int k=re;
if(k<0)del(1,1,n,-k);
else add(1,1,n,k);
}
printf("%d",find(1,1,n));
return 0;
}
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
int n;
const int N = 3e4 + 10;
int w[N],c[N];
int _left[N],_right[N];
int s[N << 2];
void pushup(int u){
s[u] = s[u<<1] + s[u<<1|1];
}
void change(int u,int l,int r,int pos){
if(l == r && l == pos){
s[u]++;
return;
}
int mid = l + r >> 1;
if(mid >= pos) change(u<<1,l,mid,pos);
else change(u<<1|1,mid+1,r,pos);
pushup(u);
}
int query(int u,int l,int r,int L,int R){
if(L > R) return 0;
if(L<=l && r<=R) return s[u];
int mid = l + r >> 1;
int tot = 0;
if(mid >= L) tot += query(u<<1,l,mid,L,R);
if(mid < R) tot += query(u<<1|1,mid+1,r,L,R);
return tot;
}
signed main(){
cin >> n;
for(int i=1;i<=n;i++){
cin >> w[i];
c[i] = w[i];
}
sort(c+1,c+n+1);
for(int i=1;i<=n;i++){
w[i] = lower_bound(c+1,c+n+1,w[i]) - c;
}
for(int i=1;i<=n;i++){
_left[i] = query(1,1,n,1,w[i]-1);
change(1,1,n,w[i]);
}
memset(s,0,sizeof s);
for(int i=n;i>=1;i--){
_right[i] = query(1,1,n,w[i]+1,n);
change(1,1,n,w[i]);
}
int res = 0;
for(int i=1;i<=n;i++) res += _left[i] * _right[i];
cout << res << endl;
return 0;
}