This is not the end.

0%

BZOJ3289 Mato的文件管理

Posted on Edited on

Sol

设 $s(l_1,r_1,l_2,r_2) = \sum_{i\in [l_1,r_1]} \sum_{j\in [l_2,r_2]} [i < j \wedge a_i > a_j]$ 。

考虑莫队算法，当右端点从$r-1$移动到$r$的时候，答案的改变量是

第一项只与 $r$ 有关，可以预处理；第二项中， $[1,l-1]$ 是整个序列的一段前缀。我们把所有第二项的询问都离线下来，然后扫描线处理。注意到总共有 $O(n)$ 次修改以及 $O(n\sqrt n)$ 次询问，我们用修改 $O(\sqrt n)$ ，查询 $O(1)$ 的分块，即可在 $O(n\sqrt n)$ 的复杂度解决问题。

右端点的左移、左端点的移动都是同理。

总时间复杂度 $O(n\sqrt n)$ ，空间复杂度 $O(n)$ 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=5e4+10;
const int M=310;
int n,m,a[N],b[N];
ll sl[N],sr[N],qans[N];
int bel[N];

namespace BIT {
	int c[N];
	void init() { for(int i=1;i<=m;++i) c[i]=0; }
	void I(int i) { for(;i<=m;i+=i&-i) c[i]++; }
	int Q(int i) { int ans=0; for(;i;i-=i&-i) ans+=c[i]; return ans; }
}

struct WRY {
	int l,r,id;
}Q[N];
bool cmpQ(WRY A,WRY B) { return bel[A.l]==bel[B.l]?(bel[A.l]&1?A.r<B.r:A.r>B.r):A.l<B.l; }
struct Qry {
	int l,r,id,ty;
};
vector<Qry> Pl[N],Pr[N];
namespace sol2 {
	int bel[N];
	int s1[M],s0[N];
	void I(int x) {
		for(int i=x;bel[i]==bel[x];++i) s0[i]++;
		for(int i=bel[x];i<=bel[m];++i) s1[i]++;
	}
	int Q(int x) { return s1[bel[x]-1]+s0[x]; }
	void main() {
		int T=ceil(sqrt(m));
		for(int i=1;i<=m;++i) bel[i]=(i-1)/T+1;
		for(int i=1;i<=n;++i) {
			I(m-a[i]+1);
			for(int j=0;j<Pl[i].size();++j)
				for(int x=Pl[i][j].l;x<=Pl[i][j].r;++x)
					qans[Pl[i][j].id]+=Pl[i][j].ty*Q(m-a[x]+1);
		}
		for(int i=0;i<=m;++i) s0[i]=0;
		for(int i=0;i<=bel[m];++i) s1[i]=0;
		for(int i=n;i>=1;--i) {
			I(a[i]);
			for(int j=0;j<Pr[i].size();++j)
				for(int x=Pr[i][j].l;x<=Pr[i][j].r;++x)
					qans[Pr[i][j].id]+=Pr[i][j].ty*Q(a[x]);
		}
	}		
}
int cid,L,R;
void addR(int t) {
	qans[cid]+=t*sr[R];
//	Pl[L-1].PB(MP(R,-t*cid));
}
void addL(int t) {	
	qans[cid]+=t*sl[L];
//	Pr[R+1].PB(MP(L,-t*cid));
}
int main() {
	rd(n);
	for(int i=1;i<=n;++i) rd(a[i]),b[i]=a[i];
	sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
	
	for(int i=1;i<=n;++i) sr[i]=BIT::Q(m-a[i]+1),BIT::I(m-a[i]+1); BIT::init();
	for(int i=n;i>=1;--i) sl[i]=BIT::Q(a[i]),BIT::I(a[i]);
	
	int T=ceil(sqrt(n));
	for(int i=1;i<=n;++i) bel[i]=(i-1)/T;
	
	int q; rd(q);
	for(int i=1;i<=q;++i) rd(Q[i].l),rd(Q[i].r),Q[i].id=i;
	sort(Q+1,Q+q+1,cmpQ);
	L=1,R=0;
	for(int i=1;i<=q;++i) {
		cid=Q[i].id;
		if(R<Q[i].r) Pl[L-1].PB((Qry){R+1,Q[i].r,cid,-1});
		if(R>Q[i].r) Pl[L-1].PB((Qry){Q[i].r+1,R,cid,1});
		while(R<Q[i].r) R++,addR(1);
		while(R>Q[i].r) addR(-1),R--;
		if(L>Q[i].l) Pr[R+1].PB((Qry){Q[i].l,L-1,cid,-1});
		if(L<Q[i].l) Pr[R+1].PB((Qry){L,Q[i].l-1,cid,1});
		while(L>Q[i].l) --L,addL(1);
		while(L<Q[i].l) addL(-1),L++;
	}
	sol2::main();
	for(int i=1;i<=q;++i) qans[Q[i].id]+=qans[Q[i-1].id];
	for(int i=1;i<=q;++i) printf("%lld\n",qans[i]);
	return 0;
}