【SOJ 1020】逆序对统计

题目传送门:http://oi.cdshishi.net:8080/Problem/1020

这货,本来以为是裸的主席树
结果被卡空间
最后还是只有写优化的主席树
另外,值域会爆int

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int M = 19000000;
const int N = 260000+9;

int n,m,POS[N],T;
LL vout,arr[N],NV[N],hash[N];

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

namespace Chair_Tree{
	#define CT Chair_Tree
	#define lowbit(x) ((x)&-(x))
	int ch[M][2],sz[M],root[N*2],cnt,ans_tmp;
	
	void modify(int p, int &w, int v, int l, int r, int delta) {
		w = ++cnt; sz[w] = sz[p] + delta; 
		memcpy(ch[w],ch[p],sizeof(ch[w])); 
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (v < mid) modify(ch[p][0],ch[w][0],v,l,mid-1,delta);
			else modify(ch[p][1],ch[w][1],v,mid,r,delta);
		}	
	}
	
	inline void modify(int pos, int val, int delta){
		for (int i=pos;i<=n;i+=lowbit(i))
			modify(root[i],root[i],val,1,T,delta);
	}
	
	inline void build(){
		for (int i=1;i<=n;i++) 
			modify(root[i-1+n+1],root[i+n+1],arr[i],1,T,1);
	}
	
	void query(int w, int l, int r, int L, int R) {
		if (!w) return;
		else if (l <= L && R <= r) ans_tmp += sz[w];
		else {
			int mid = L + R + 1 >> 1;
			if (l < mid) query(ch[w][0],l,r,L,mid-1);
			if (mid <= r) query(ch[w][1],l,r,mid,R);
		}	
	}
	
	inline int query(int w, int l, int r) {
		ans_tmp = 0;
		query(w,l,r,1,T);
		return ans_tmp;
	}
	
	inline int query(int l ,int r, int L, int R){
		if (l > r || L > R) return 0; int ret = 0;
		for (int i=r;i;i-=lowbit(i)) ret += query(root[i],L,R);
		for (int i=l-1;i;i-=lowbit(i)) ret -= query(root[i],L,R);
		ret += query(root[n+r+1],L,R);
		ret -= query(root[n+l-1+1],L,R);
		return ret;
	}
};

int main(){
	n = read(); for (int i=1;i<=n;i++) arr[i] = hash[++T] = read(); 
	m = read(); for (int i=1;i<=m;i++) POS[i] = read(), NV[i] = hash[++T] = read();
	sort(hash+1,hash+1+T); T = unique(hash+1,hash+1+T) - hash - 1;
	for (int i=1;i<=n;i++) arr[i] = lower_bound(hash+1,hash+T+1,arr[i]) - hash;
	for (int i=1;i<=m;i++) NV[i] = lower_bound(hash+1,hash+T+1,NV[i]) - hash;
	
	CT::build();
	for (int i=1;i<=n;i++) vout += CT::query(1,i-1,arr[i]+1,T);
	for (int i=1,pos,nv;m;m--,i++) {
		pos = POS[i]; nv = NV[i];
		vout -= CT::query(1,pos-1,arr[pos]+1,T);
		vout -= CT::query(pos+1,n,1,arr[pos]-1);
		vout += CT::query(1,pos-1,nv+1,T);
		vout += CT::query(pos+1,n,1,nv-1);
		CT::modify(pos, arr[pos], -1);
		CT::modify(pos, nv, 1);
		arr[pos] = nv;
		cout<<vout<<endl;
	}
	return 0;
}

看其他人的代码,貌似还有非主席树的做法?
原来是不清真的分块…….E}QOU7H{JN1WP11[S43%HHR

2 thoughts to “【SOJ 1020】逆序对统计”

  1. Heya this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML. I’m starting a blog soon but have no coding skills so I wanted to get advice from someone with experience. Any help would be greatly appreciated!

Leave a Reply

Your email address will not be published. Required fields are marked *