Orz黄学长,蒟蒻在黄学长的带领下,通过阅读黄学长的代码!终于会了这道题! 首先我想先说一下这道题的思路(准确来说是黄学长的)。 很明显,树状数组应该不用讲吧!关键是内存怎么开,维护一些什么样的数据? 其实我们通过观察,很快可以发现,你维护被删的数比维护所有的数轻松多了(不管是空间上,还是时间上)。所以我们就可以从这方面想!(其实我一开始的思路,因为这道题我已经看过很久了,一直想写,毕竟是白书里面的一道例题嘛!一开始,蒟蒻的我是打算这样的用树状数组套权值线段树,并且是维护所有的数,我发现空间不够我开的(或许是我太弱,有大神的话请指教一下。)。好像是因为我维护所有的数才错了,(而且就算要维护,也是动态开点第维护)仔细一想黄学长就是树状数组套权值线段树啊!太弱了我啊!too young too simple 。而且宝宝,开点的时候,一开始只开了一百万,WA掉了,后来看了黄学长开了五百万,自己再仔细一想,logN = 17 , 因为是树套树所以是 logN的平方, 还要乘上操作的次数M, 所以………………,我又错了。加油了多积累经验)。
1 #include
2 #include
3 #include
4 #define rep(i,j,k) for(int i = j; i <= k; i++)
5 #define down(i,j,k) for(int i = j; i >= k; i--)
6 #define lc c[k][0]
7 #define rc c[k][1]
8 #define N 5000005
9 #define ll long long
10 #define maxn 102333
11 using namespace std;
12
13 int t[maxn], c[N][2], root[maxn], sum[N], a1[maxn], a2[maxn], pos[maxn], num[maxn];
14 int A[30], B[30];
15
16 int cnt = 0, n, m;
17 int read()
18 {
19 int s = 0, t = 1; char c = getchar();
20 while( !isdigit(c) ){
21 if( c == ‘-‘ ) t = -1; c = getchar();
22 }
23 while( isdigit(c) ){
24 s = s * 10 + c - ‘0‘; c = getchar();
25 }
26 return s * t;
27 }
28 int lower(int x) {return x & (-x); }
29
30 int get_num(int x)
31 {
32 int ans = 0;
33 for( ; x; x -= lower(x)) ans += t[x];
34 return ans;
35 }
36
37 void update(int&k,int l,int r,int num)
38 {
39 if( !k ) k = ++cnt;
40 sum[k]++;
41 if( l == r ) return;
42 int mid = (l+r)>>1;
43 if( mid 1,r,num);
44 else update(lc,l,mid,num);
45 }
46
47 ll get_more(int x,int y,int num)
48 {
49 A[0] = B[0] = 0; x--; ll tmp = 0;
50 for( ; x; x -= lower(x) ) A[++A[0]] = root[x];
51 for( ; y; y -= lower(y) ) B[++B[0]] = root[y];
52 int l = 1, r = n;
53 while( l != r ){
54 int mid = (l+r)>>1;
55 if( num <= mid ) {
56 rep(i,1,A[0]) tmp -= sum[c[A[i]][1]];
57 rep(i,1,B[0]) tmp += sum[c[B[i]][1]];
58 rep(i,1,A[0]) A[i] = c[A[i]][0];
59 rep(i,1,B[0]) B[i] = c[B[i]][0];
60 r = mid;
61 }
62 else {
63 rep(i,1,A[0]) A[i] = c[A[i]][1];
64 rep(i,1,B[0]) B[i] = c[B[i]][1];
65 l = mid+1;
66 }
67 }
68 return tmp;
69 }
70
71 ll get_less(int x,int y,int num)
72 {
73 A[0] = B[0] = 0; x--; ll tmp = 0;
74 for( ; x; x -= lower(x)) A[++A[0]] = root[x];
75 for( ; y; y -= lower(y)) B[++B[0]] = root[y];
76 int l = 1, r = n;
77 while( l != r ){
78 int mid = (l+r)>>1;
79 if( num > mid ){
80 rep(i,1,A[0]) tmp -= sum[c[A[i]][0]];
81 rep(i,1,B[0]) tmp += sum[c[B[i]][0]];
82 rep(i,1,A[0]) A[i] = c[A[i]][1];
83 rep(i,1,B[0]) B[i] = c[B[i]][1];
84 l = mid + 1;
85 }
86 else {
87 rep(i,1,A[0]) A[i] = c[A[i]][0];
88 rep(i,1,B[0]) B[i] = c[B[i]][0];
89 r = mid;
90 }
91 }
92 return tmp;
93 }
94
95 int main()
96 {
97 n = read(), m = read(); ll ans = 0;
98 rep(i,1,n){
99 num[i] = read(); pos[num[i]] = i;
100 a1[i] = get_num(n)-get_num(num[i]-1);
101 ans += a1[i];
102 for(int x = num[i]; x <= n; x += lower(x) ) t[x]++;
103 }
104 memset(t,0,sizeof(t));
105 down(i,n,1){
106 int x = num[i];
107 a2[i] = get_num(x-1);
108 for( ; x <= n; x += lower(x) ) t[x]++;
109 }
110 rep(i,1,m){
111 printf("%lld\n", ans);
112 int x = read(); int po = pos[x];
113 ans -= (a1[po] + a2[po] - get_more(1,po-1,x) - get_less(po+1,n,x));
114 for( ; po <= n; po += lower(po) ) update(root[po],1,n,x);
115 }
116 return 0;
117 }
据翻博客,有人分块A掉了,我不信,怎么可能呢?可是这怎么知道呢?还是还要敲的。很明显,以比树套树的代码慢一倍的代价(大约),A掉了。哈哈!到现在好像还真的没怎么看过分块A不掉的题(不过肯定是有的,是蒟蒻写的题太少,蒟蒻写的题分块几乎都能写),但是写这个不利于自身水平的提高啊!(不到迫不得已,还是少写分块吧!)
1 #include
2 #include
3 #include
4 #include
5 #include
6 #define ll long long
7 #define rep(i,j,k) for(int i = j; i <= k; i++)
8 #define down(i,j,k) for(int i = j; i >= k; i--)
9 #define maxn 323
10 #define inf 0x7fffffff
11 using namespace std;
12
13 vector<int> s[maxn];
14 int pos[100233], v[100233], t[100233];
15 bool vis[100233];
16 int n, m;
17
18 int lower(int x ) { return x & (-x); }
19 int getans(int x)
20 {
21 int ans = 0; for(; x; x -= lower(x) ) ans += t[x];
22 return ans;
23 }
24
25 int read()
26 {
27 int s = 0, t = 1; char c = getchar();
28 while( !isdigit(c) ){
29 if( c == ‘-‘ ) t = -1; c = getchar();
30 }
31 while( isdigit(c) ){
32 s = s * 10 + c - ‘0‘; c = getchar();
33 }
34 return s * t;
35 }
36
37 int get_max(int r,int num)
38 {
39 int last = r / maxn; int tmp = 0;
40 rep(i,0,last-1) {
41 tmp += (s[i].size()-1-(upper_bound(s[i].begin(),s[i].end(),num)-s[i].begin()));
42 }
43 int begin = last*maxn;
44 rep(i,begin,r){
45 if( !vis[i] && v[i] > num ) tmp++;
46 }
47 //cout<<" a "<
48 return tmp;
49 }
50
51 int get_min(int l,int num)
52 {
53 int begin = l / maxn; int tmp = 0;
54 rep(i,begin+1,n/maxn){
55 tmp += (lower_bound(s[i].begin(),s[i].end(),num)-s[i].begin());
56 }
57 int last = (begin+1)*maxn-1;
58 rep(i,l,min(last,n)){
59 // cout<60 // cout<<"k "<
61 if( !vis[i] && v[i] ;
62 }
63 // cout<<" i "<
64 return tmp;
65 }
66
67 void update(int pos,int num)
68 {
69 int x = pos / maxn;
70 // cout<<"U "<
71 s[x].erase(lower_bound(s[x].begin(),s[x].end(),num));
72 vis[pos] = 1;
73 }
74
75 int main()
76 {
77 n = read(), m = read(); ll ans = 0;
78 rep(i,0,maxn) s[i].push_back(inf);
79 rep(i,1,n){
80 v[i] = read(); pos[v[i]] = i; s[i/maxn].insert(lower_bound(s[i/maxn].begin(),s[i/maxn].end(),v[i]),v[i]);
81 ans += (getans(n)-getans(v[i]-1));
82 for(int x = v[i]; x <= n ; x += lower(x) ) t[x]++;
83 }
84 memset(t,0,sizeof(t));
85 rep(i,1,m){
86 printf("%lld\n", ans);
87 int x = read(), po = pos[x];
88 ans -= (get_max(po-1,x)+get_min(po+1,x));
89 update(po,x);
90 //cout<
91 }
92 return 0;
93 }