CF1540D Inverse Inversions

题面传送门

首先先来想一个\(O(nq)\)的暴力。

显然我们有\(O(n\log n)\)的贪心：每次选取为\(0\)的最后一个填入\(n\)，然后将这个数后面的\(B_i\)减一，然后将\(n\)减一。这样填到这个位置就是这个答案。

但是这个东西显然不好维护并且我们要求的只是一个单点的权值，不用这么大费周章。

我们考虑大于当前\(x\)的个数，显然在\(x\)前面的有恰好\(B_x\)个大于\(x\)，然后后面因为前面删掉了\(B_x\)个因此所有小于等于\(B_x\)的都会比这个点先填。但是这不充分，我们发现有一些点可能原来是大于\(B_x\)的，但是由于前面删了点所以最后会比\(x\)删得早，进一步的，我们发现其实就是维护下面这个东西：

Ans=B[x];for(j=x+1;j<=n;j++) if(B[j]<=Ans) Ans++;printf("%d\n",n-Ans);

\(10^5\)又5s想到分块，我们考虑维护出一个数经过每个块以后出来会加上多少，这个显然是分\(B\)段的一次函数，可以用分治做到\(O(B)\)或\(O(B\log B)\)求出，然后查询的时候散块暴力查询，整块直接二分即可。

时间复杂度\(O(n\sqrt n\log n)\)，偷懒写了个\(O(B\log B)\)的东西。

实际实现的时候发现其实这个东西可以写成一个线段树的形式。因为线段树本身是一种分治结构，因此可以在线段树上Update的时候如果一个节点的大小大于\(B\)就不Update，否则就Update，查询的时候一直递归到节点大小小于等于\(B\)再二分。这样会好写很多。

code:

#include<bits/stdc++.h>
#include<iostream>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=1e5+5,M=N*4+5,K=1e5+5,mod=998244353,Mod=mod-1,INF=2e9+7;const db eps=1e-5;mt19937 rnd(time(0));
int n,m,k,B[N],op,x,y,Ans;
namespace Tree{
	#define ls v<<1
	#define rs v<<1|1
	struct Node{int x,w,S;bool operator <(const Node &B)const{return x<B.x;};};
	vector<Node> f[M],g;int Si[M];void Up(int v){
		if(Si[v]>k) return;g=f[ls];for(Node i:f[rs]) {
			int l=-1,r=f[ls].size(),mid;while(l+1<r) mid=l+r>>1,(f[ls][mid].S-f[ls][mid].w+f[ls][mid].x-1<i.x?l:r)=mid;g.PB((Node){max(i.x-(~l?f[ls][l].S:0),~l?f[ls][l].x:0),i.w,0});
		} sort(g.begin(),g.end());f[v].clear();f[v].shrink_to_fit();for(int i=0;i<g.size();i++) if(!i||g[i].x^g[i-1].x) f[v].PB(g[i]);else f[v][f[v].size()-1].w+=g[i].w;
		for(int i=0;i<f[v].size();i++) f[v][i].S=f[v][i].w+(i?f[v][i-1].S:0);
	}
	void BD(int l=1,int r=n,int v=1){Si[v]=r-l+1;if(l==r) {f[v].PB((Node){B[l],1,1});return;}int m=l+r>>1;BD(l,m,ls);BD(m+1,r,rs);Up(v);}
	void Ins(int x,int y,int l=1,int r=n,int v=1){if(l==r) {f[v].clear();f[v].PB((Node){y,1,1});return;}int m=l+r>>1;x<=m?Ins(x,y,l,m,ls):Ins(x,y,m+1,r,rs);Up(v);}
	void Qry(int x,int y,int &z,int l=1,int r=n,int v=1){if(x<=l&&r<=y&&Si[v]<=k) {/*cerr<<l<<' '<<r<<' '<<(*f[v].begin()).x<<'\n';*/auto p=UB(f[v].begin(),f[v].end(),(Node){z,0,0});if(p==f[v].end()) --p,z+=(*p).S;else z+=(*p).S-(*p).w;return;}int m=l+r>>1;x<=m&&(Qry(x,y,z,l,m,ls),0);y>m&&(Qry(x,y,z,m+1,r,rs),0);}
}
int main(){
	freopen("1.in","r",stdin);
	int i,j;scanf("%d",&n);k=max(sqrt(n/2),1.0);for(i=1;i<=n;i++) scanf("%d",&B[i]);Tree::BD();scanf("%d",&m);while(m--){
		scanf("%d%d",&op,&x);if(op==1) {scanf("%d",&y);Tree::Ins(x,B[x]=y);continue;}
		Ans=B[x];x^n&&(Tree::Qry(x+1,n,Ans),0);printf("%d\n",n-Ans);
	}
}

原文地址：http://www.cnblogs.com/275307894a/p/16910231.html