BZOJ 3211: 花神游历各国

一个数n<=10^9 在被sqrt 7次左右就会变成1 所以这题可以用一个并查集维护一段连续为1的数 修改的时候暴力修改 遇到一个为1就直接跳到这段的末尾 查询用一个线段树维护就行了

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
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 100005;

ll a[maxn], t[maxn * 4], n, m, fa[maxn], b[maxn];

ll getfa(ll now)
{
  return (!fa[now]) ? now : (fa[now] = getfa(fa[now]));
}

void build(ll l, ll r, ll now)
{
  if (l == r)
  {
    t[now] = a[l];
    return;
  }
  ll mid = (l + r) / 2;
  build(l, mid, now * 2);
  build(mid + 1, r, now * 2 + 1);
  t[now] = t[now * 2] + t[now * 2 + 1];
}

void modify(ll l, ll r, ll now, ll lr, ll v)
{
  if (l == r)
  {
    t[now] = v;
    return;
  }
  ll mid = (l + r) / 2;
  if (lr <= mid) modify(l, mid, now * 2, lr, v);
  else modify(mid + 1, r, now * 2 + 1, lr, v);
  t[now] = t[now * 2] + t[now * 2 + 1];
}

ll query(ll l, ll r, ll now, ll lf, ll rt)
{
  if (l >= lf && r <= rt) return t[now];
  ll mid = (l + r) / 2, ans = 0;
  if (lf <= mid) ans += query(l, mid, now * 2, lf, rt);
  if (rt >= mid + 1) ans += query(mid + 1, r, now * 2 + 1, lf, rt);
  return ans;
}

ll sq(ll a)
{
  return (ll)floor(sqrt((double)a));
}

void modi(ll l, ll r)
{
  for (ll i = l; i <= r; i = (!b[i]) ? (i + 1) : (getfa(i) + 1))
  {
    if (b[i]) continue;
    a[i] = sq(a[i]);
    modify(1, n, 1, i, a[i]);
    if (a[i] <= 1)
    {
      b[i] = 1;
      if (b[i - 1]) fa[getfa(i - 1)] = i;
      if (b[i + 1]) fa[i] = getfa(i + 1);
    }
  }
}

int main()
{
  freopen("input.in", "r", stdin);
  freopen("output.out", "w", stdout);
  scanf("%lld", &n);
  for (ll i = 1; i <= n; ++i)
    scanf("%lld", &a[i]);
  build(1, n, 1);
  scanf("%lld", &m);
  for (ll i = 0; i < m; ++i)
  {
    ll x, l, r;
    scanf("%lld%lld%lld", &x, &l, &r);
    if (x == 1) printf("%lld\n", query(1, n, 1, l, r));
    else modi(l, r);
  }
  fclose(stdin);fclose(stdout);
}

全国互虐 TEST 5.19【差额】

先求dfs序
对于一个询问(u, v) 可以看成一个点(dfs序上u的起始位置, dfs序上v的起始位置)

一个询问 其实就是询问某个矩形内的点数
对于询问(u, v) 设p=lca(u, v)

如果p != u && p != v则
  能包含它的询问的两个点
  一定一个在u的子树 一个在v的子树
  即为(dfs[u].begin~dfs[u].end, dfs[v].begin~dfs[v].end)范围内的点
否则
  设u == p
  能包含它的询问的两个点
  一定一个在v的子树 一个不在u向v路径上的第二个点的子树
  这样是两个矩形

这些查询 把点排序后用线段树维护就行了
对于一个矩形询问 拆成两个进行询问 差分 你懂的。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 100005;

struct line
{
  int to, next;
}li[maxn * 2];

struct inout
{
  int in, out;
  inout(int a = 0, int b = 0) : in(a), out(b) {}
}a[maxn];

struct point
{
  int x, y;
  point(int a = 0, int b = 0) : x(a), y(b) {}
}Q[maxn];

int dfsq[maxn * 2], t[maxn * 8], n, m, be[maxn], fa[maxn][20], d[maxn], tot, l, tot2, to;
ll ans[maxn];

struct query
{
  int l, r, x, v, to;
  query(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) : l(a), r(b), x(c), v(d), to(e) {}
}qu[maxn * 3];

queue<int> q;

int lca(int u, int v)
{
  if (d[u] < d[v]) swap(u, v);
  int i;
  while (d[u] > d[v])
  {
    for (i = 0; d[fa[u][i]] >= d[v]; ++i);
    u = fa[u][i - 1];
  }
  while (u != v)
  {
    for (i = 1; fa[u][i] != fa[v][i]; ++i);
    u = fa[u][i - 1];
    v = fa[v][i - 1];
  }
  return u;
}

void dfs(const int &now)
{
  a[now].in = tot;
  dfsq[tot++] = now;
  for (int i = be[now]; i; i = li[i].next)
  {
    if (li[i].to == fa[now][0]) continue;
    dfs(li[i].to);
  }
  a[now].out = tot;
  dfsq[tot++] = now;
}

void makeline(int fr, int to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}

bool cmp(point a, point b) { return a.x < b.x; }
bool cmp2(query a, query b) { return a.x < b.x; }

void insert(int l, int r, int now, int lr)
{
  if (l == r)
  {
    ++t[now];
    return;
  }
  int mid = (l + r) / 2;
  if (lr <= mid) insert(l, mid, now * 2, lr);
  else insert(mid + 1, r, now * 2 + 1, lr);
  t[now] = t[now * 2] + t[now * 2 + 1];
}

int quer(int l, int r, int now, int lf, int rt)
{
  if (l >= lf && r <= rt) return t[now];
  int mid = (l + r) / 2, ans = 0;
  if (lf <= mid) ans += quer(l, mid, now * 2, lf, rt);
  if (rt >= mid + 1) ans += quer(mid + 1, r, now * 2 + 1, lf, rt);
  return ans;
}

ll gcd(ll a, ll b)
{
  return (!b) ? a : gcd(b, a % b);
}

int getfa(int u, int de)
{
  int i;
  while (d[u] > de)
  {
    for (i = 0; d[fa[u][i]] >= de; ++i);
    u = fa[u][i - 1];
  }
  return u;
}

int main()
{
  freopen("painting.in", "r", stdin);
  freopen("painting.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n; ++i)
  {
    int fr, to;
    scanf("%d%d", &fr, &to);
    makeline(fr, to);
    makeline(to, fr);
  }
  q.push(1);
  d[1] = 1;
  while (!q.empty())
  {
    int now = q.front();
    q.pop();
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (to == fa[now][0]) continue;
      fa[to][0] = now;
      d[to] = d[now] + 1;
      q.push(to);
    }
    for (int i = fa[now][0], j = 0; i; i = fa[i][j++])
      fa[now][j + 1] = fa[i][j];
  }
  dfs(1);
  for (int i = 0; i < m; ++i)
  {
    int fr, to;
    scanf("%d%d", &fr, &to);
    if (a[fr].in > a[to].in) swap(fr, to);
    Q[i * 2] = point(a[fr].in, a[to].in);
    Q[i * 2 + 1] = point(a[to].in, a[fr].in);
    if (lca(fr, to) == fr)
    {
      int t = getfa(to, d[fr] + 1);
      qu[tot2++] = query(a[to].in, a[to].out, tot - 1, 1, i);
      qu[tot2++] = query(a[to].in, a[to].out, a[t].out, -1, i);
      qu[tot2++] = query(a[to].in, a[to].out, a[t].in - 1, 1, i);
    }
    else
    {
      qu[tot2++] = query(a[to].in, a[to].out, a[fr].in - 1, -1, i);
      qu[tot2++] = query(a[to].in, a[to].out, a[fr].out, 1, i);
    }
  }
  sort(Q, Q + m * 2, cmp);
  sort(qu, qu + tot2, cmp2);
  int k1 = 0, k2 = 0;
  for (; k2 < tot2 && qu[k2].x == -1; ++k2);
  for (int i = 0; i < tot; ++i)
  {
    for (; k1 < m * 2 && Q[k1].x <= i; ++k1) insert(0, tot, 1, Q[k1].y);
    for (; k2 < tot2 && qu[k2].x <= i; ++k2)
      ans[qu[k2].to] += quer(0, tot, 1, qu[k2].l, qu[k2].r) * qu[k2].v;
  }/*
  for (int i = 0; i < m; ++i) printf("%d ", ans[i]);
cout << endl;*/

  ll ANS = 0;
  for (int i = 0; i < m; ++i)
    ANS += ans[i] - 1;
  if (ANS == 0) printf("0/1");
  else
  {
    ll t = gcd(ANS, (ll)m * (m - 1) / 2);
    printf("%I64d/%I64d", ANS / t, (ll)m * (m - 1) / 2 / t);
  }
  fclose(stdin);fclose(stdout);
}

带插入区间k大值

区间k大 主席树即可乱虐
带插入的话 可以想到用平衡树套权值线段树解决
但是如果用splay 每次要改变很多节点
就会要重建很多节点上的权值线段树
这样就会TLE
这么避免这个情况呢?
————替罪羊树(可以参见VFleaKing的论文《对无旋转操作的平衡树的一些探究》)
替罪羊树的思想就是 没有旋转操作
如果某棵子树过于不平衡 则直接重建这颗子树
看似非常暴力 但是通过势能分析 可以证明每次复杂度是均摊logn的
替罪羊树判断不平衡的方法有两种
一 高度平衡
二 子节点个数平衡
我用的是第二个 好像这个也比较好写
定义一个常数A 0.5 <= A <= 1 定义某节点为根的子树大小为sum 左子树大小为left_sum 右子树大小为right_sum 如果max(left_sum, right_sum) > sum * A
则称以这个节点为根的子树不平衡 需要暴力重建

现在细化一下如何暴力重建
这个看似很随意的乱搞就可以
其实也不是很随意的。。

第一步:
把这棵子树表示为一条链
定义函数link(n, k)
表示把以n为根的子树拆成一条链
并在右边连上y 并返回最左边的节点编号
实现如下:

1
2
3
4
5
6
7
int link(int now, int z)
{
  if (!now) return z;
  int y = link(t[now].r, z);
  t[now].rt = y;
  return link(t[now].l, now);
}

第二步:
把这条链建成一棵绝对平衡的树
定义函数build(n, k)
表示把以n这个节点为开头的 链上的k个节点建成一棵树
并满足这颗树的根没有右儿子 返回树的根
实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int build(int now, int n)
{
  if (n == 1)
  {
    t[now].l = t[now].r = 0;
    return now;
  }
  int mid = n / 2;
  int l = build(now, mid);
  int r = build(t[l].rt, n - mid);
  t[l].r = t[r].l;
  t[r].l = l;
  return r;
}

第三步:
对新树上的所有节点做处理
这个用一个dfs就可以实现 就不多说
只说一下关于对于每个节点的权值线段树的建立
可以用一个函数把两个子树合并 再把这个节点的权值插入进去即可

怎么比较好的调用这些函数?

1
2
3
4
5
6
7
8
9
int rebuild(int now)
{
  int n = t[now].sum, p = MAXN - 1;
  t[MAXN - 1] = node(0, 0, 0, 0, 0);
  int k = link(now, p);
  build(k, n + 1);
  bld(t[p].l);
  return t[p].l;
}

就是新建一个节点p 把以now为根的子树形成的链接在p的左边
然后建树后会得到一个以p为根的 只有左子树的树
p的左子树就是要的树

以上就是替罪羊树的实现过程

对于一个询问 可以把它拆成几个节点代表的权值线段树和几个散点 可以证明这些是log级的
然后把这些记下来 像普通的主席树的做法就可以求出第k大值了

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const double A = 0.618;
const int MAXN = 80000;
 
struct node2
{
  int l, r, sum;
  node2(int a = 0, int b = 0, int c = 0) : l(a), r(b), sum(c) {}
}t2[20000005];
 
struct node
{
  int l, r, v, sum, root, rt;
  node(int a = 0, int b = 0, int _v = 0, int c = 0, int d = 0, int _rt = 0) : l(a), r(b), v(_v), sum(c), root(d), rt(_rt) {}
}t[MAXN];
 
int n, m, root, tot, tot2, la, temp[MAXN], tot3, tot4, s[20000005];
 
int mknode(int l, int r, int v, int sum, int root)
{
  return t[++tot] = node(l, r, v, sum, root), tot;
}
 
int mknode2(int l, int r, int sum)
{
  int now = s[--tot4];
  return t2[now] = node2(l, r, sum), now;
}
 
int mdf(int l, int r, int now, int v, int c)
{
  if (!now) now = mknode2(0, 0, 0);
  if (l == r)
  {
    t2[now].sum += c;
    return now;
  }
  int mid = (l + r) / 2;
 
  if (v <= mid) t2[now].l = mdf(l, mid, t2[now].l, v, c);
  else t2[now].r = mdf(mid + 1, r, t2[now].r, v, c);
 
  t2[now].sum = t2[t2[now].l].sum + t2[t2[now].r].sum;
 
  if (t2[now].l && !t2[t2[now].l].sum)
  {
    s[tot4++] = t2[now].l;
    t2[now].l = 0;
  }
  if (t2[now].r && !t2[t2[now].r].sum)
  {
    s[tot4++] = t2[now].r;
    t2[now].r = 0;
  }
  return now;
}
 
int insert(int root, int v)
{
  mdf(0, MAXN, root, v, 1);
  return root;
}
 
int del(int root, int v)
{
  mdf(0, MAXN, root, v, -1);
  return v;
}
 
int link(int now, int z)
{
  if (!now) return z;
  int y = link(t[now].r, z);
  t[now].rt = y;
  return link(t[now].l, now);
}
 
int build(int now, int n)
{
  if (n == 1)
  {
    t[now].l = t[now].r = 0;
    return now;
  }
  int mid = n / 2;
  int l = build(now, mid);
  int r = build(t[l].rt, n - mid);
  t[l].r = t[r].l;
  t[r].l = l;
  return r;
}
 
void clear(int now)
{
  if (!now) return;
  clear(t2[now].l), clear(t2[now].r);
  s[tot4++] = now;
}
 
int together(int now1, int now2, int b)
{
  if (!now1 && !now2) return b ? mknode2(0, 0, 0) : 0;
  return mknode2(together(t2[now1].l, t2[now2].l, 0), together(t2[now1].r, t2[now2].r, 0), t2[now1].sum + t2[now2].sum);
}
 
void bld(int now)
{
  if (!now) return;
  bld(t[now].l), bld(t[now].r);
  t[now].sum = t[t[now].l].sum + t[t[now].r].sum + 1;
  clear(t[now].root);
  t[now].root = together(t[t[now].l].root, t[t[now].r].root, 1);
  insert(t[now].root, t[now].v);
}
 
int rebuild(int now)
{
  int n = t[now].sum, p = MAXN - 1;
  t[MAXN - 1] = node(0, 0, 0, 0, 0);
  int k = link(now, p);
  build(k, n + 1);
  bld(t[p].l);
  return t[p].l;
}
 
int ins(int now, int p, int v)
{
  if (!root)
  {
    root = mknode(0, 0, v, 1, insert(mknode2(0, 0, 0), v));
    return root;
  }
  insert(t[now].root, v);
  ++t[now].sum;
 
  if (t[t[now].l].sum >= p - 1)
    if (t[now].l) t[now].l = ins(t[now].l, p, v);
    else t[now].l = mknode(0, 0, v, 1, insert(mknode2(0, 0, 0), v));
  else
    if (t[now].r) t[now].r = ins(t[now].r, p - 1 - t[t[now].l].sum, v);
    else t[now].r = mknode(0, 0, v, 1, insert(mknode2(0, 0, 0), v));
 
  if (max(t[t[now].l].sum, t[t[now].r].sum) >= (int)(t[now].sum * A))
    return rebuild(now);
  return now;
}
 
int modify(int now, int p, int v)
{
  insert(t[now].root, v);
  if (t[t[now].l].sum == p - 1)
  {
    int k = t[now].v;
    t[now].v = v;
    return del(t[now].root, k);
  }
 
  if (t[t[now].l].sum >= p - 1)
    return del(t[now].root, modify(t[now].l, p, v));
  else
    return del(t[now].root, modify(t[now].r, p - 1 - t[t[now].l].sum, v));
}
 
void deal(int l, int r, int now, int lf, int rt)
{
  if (l > r) return;
  if (l >= lf && r <= rt)
  {
    temp[tot3++] = t[now].root;
    return;
  }
  if (l > rt || r < lf) return;
  int k = l + t[t[now].l].sum;
  if (k >= lf && k <= rt) temp[tot3++] = -t[now].v;
  deal(l, k - 1, t[now].l, lf, rt);
  deal(k + 1, r, t[now].r, lf, rt);
}
 
int qu(int l, int r, int k)
{
  if (l == r) return l;
  int sum = 0, mid = (l + r) / 2, sum2 = 0;
  for (int i = 0; i < tot3; ++i)
    if (temp[i] > 1) sum += t2[t2[temp[i]].l].sum;
    else if (temp[i] <= 0) sum2 += ((-temp[i]) <= mid);
  if (sum + sum2 >= k)
  {
    for (int i = 0; i < tot3; ++i) if (temp[i] > 1) temp[i] = t2[temp[i]].l ? t2[temp[i]].l : 1;
    return qu(l, mid, k);
  }
  else
  {
    for (int i = 0; i < tot3; ++i) if (temp[i] > 1) temp[i] = t2[temp[i]].r ? t2[temp[i]].r : 1;
    return qu(mid + 1, r, k - sum);
  }
}
 
int query(int l, int r, int v)
{
  tot3 = 0;
  deal(1, n, root, l, r);
  return qu(0, MAXN, v);
}
 
int main()
{
  scanf("%d", &n);
  for (int i = 1; i < 20000005; ++i)
    s[tot4++] = i;
  for (int i = 1; i <= n; ++i)
  {
    int v;
    scanf("%d", &v);
    t[++tot].r = i + 1;
    t[tot].v = v;
    t[tot].root = mknode2(0, 0, 0);
  }
  t[n].r = 0; t[1].sum = n;
  root = rebuild(1);
  scanf("%d", &m);
  while (m--)
  {
    char c;
    int x, y;
    scanf("\n%c%d%d", &c, &x, &y);
    x ^= la, y ^= la;
    if (c == 'I') (root = ins(root, x, y)), ++n;
    if (c == 'M') modify(root, x, y);
    if (c == 'Q')
    {
      int k;
      scanf("%d", &k);
      k ^= la;
      printf("%d\n", la = query(x, y, k));
    }
  }
}

BZOJ 1926: [SDOI2010]粟粟的书架

这题有两部分
1:r、c<=200
这个开一个 f[x][y][k]的数组 表示(1, 1)~(x, y)矩阵里>=k的数的权值和
对一个询问做一次二分即可
2:r=1、c<=500000
无修改区间k大。。裸主席树=、=

——————code——————-

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
struct node
{
  int lf, rt, sum, num;
}t[10000000];
int f[201][201][1002], sum[201][201][1002], r, c, n, m, v[201][201], p, ss[500005], s[500005], root[500005];
int get(int x1, int y1, int x2, int y2, int k)
{
  return f[x2][y2][k] – f[x1 – 1][y2][k] – f[x2][y1 – 1][k] + f[x1 – 1][y1 – 1][k];
}
int get_s(int x1, int y1, int x2, int y2, int k)
{
  return sum[x2][y2][k] – sum[x1 – 1][y2][k] – sum[x2][y1 – 1][k] + sum[x1 – 1][y1 – 1][k];
}
int maketree(int l, int r)
{
  p++;
  if (l == r) return p;
  int mid = (l + r) / 2;
  t[p].lf = maketree(l, mid);
  t[p].rt = maketree(mid + 1, r);
  return p;
}
int ins(int now, int lr, int l, int r)
{
  p++;
  int no = p;
  t[no] = t[now];
  if (l == r)
  {
    ++t[no].num;
    t[no].sum += l;
    return no;
  }
  int mid = (l + r) / 2;
  if (lr <= mid) t[no].lf = ins(t[now].lf, lr, l, mid), t[no].rt = t[now].rt;
  else t[no].rt = ins(t[now].rt, lr, mid + 1, r), t[no].lf = t[now].lf;
  t[no].sum = t[t[no].lf].sum + t[t[no].rt].sum;
  t[no].num = t[t[no].lf].num + t[t[no].rt].num;
  return no;
}
int query(int now1, int now2, int l, int r, int h)
{
  if (l == r) return h ? (h – 1) / l + 1 : 0;
  int mid = (l + r) / 2;
  int tt = t[t[now2].rt].sum – t[t[now1].rt].sum;
  if (h >= tt) return t[t[now2].rt].num – t[t[now1].rt].num + query(t[now1].lf, t[now2].lf, l, mid, h – tt);
  else return query(t[now1].rt, t[now2].rt, mid + 1, r, h);
}
int main()
{
  cin >> r >> c >> m;
  if (r <= 200 && c <= 200)
  {
    for (int i = 1; i <= r; i++)
      for (int j = 1; j <= c; j++) scanf(“%d”, &v[i][j]);
    for (int x = 1; x <= r; ++x)
      for (int y = 1; y <= c; ++y)
      {
        for (int k = 1; k <= 1000; ++k)
          sum[x][y][k] = sum[x – 1][y][k] + sum[x][y – 1][k] – sum[x – 1][y – 1][k];
        ++sum[x][y][v[x][y]];
      }
    for (int x = 1; x <= r; ++x)
      for (int y = 1; y <= c; ++y)
        for (int k = 1000; k >= 1; –k)
          f[x][y][k] = f[x][y][k + 1] + k * sum[x][y][k],
          sum[x][y][k] = sum[x][y][k + 1] + sum[x][y][k];
    for (int i = 0; i < m; i++)
    {
      int x1, y1, x2, y2, h;
      scanf(“%d%d%d%d%d”, &x1, &y1, &x2, &y2, &h);
      if (get(x1, y1, x2, y2, 1) < h)
      {
        printf(“Poor QLW\n”);
        continue;
      }
      int l = 0;
      int r = 1001;
      while (l + 1 < r)
      {
        int mid = (l + r) / 2;
        if (get(x1, y1, x2, y2, mid) < h) r = mid;
        else l = mid;
      }
      int ans = get_s(x1, y1, x2, y2, r);
      if (r > 1 && h – get(x1, y1, x2, y2, r))
        ans += (h – get(x1, y1, x2, y2, r) – 1) / (r – 1) + 1;
      printf(“%d\n”, ans);
    }
  }
  else
  {
    n = c;
    for (int i = 1; i <= n; i++) scanf(“%d”, &s[i]), ss[i] = ss[i – 1] + s[i];
    root[0] = maketree(1, 1000);
    for (int i = 1; i <= n; i++)
      root[i] = ins(root[i – 1], s[i], 1, 1000);
    for (int i = 0; i < m; i++)
    {
      int x1, lf, x2, rt, h;
      scanf(“%d%d%d%d%d”, &x1, &lf, &x2, &rt, &h);
      if (ss[rt] – ss[lf – 1] < h)
      {
        printf(“Poor QLW\n”);
        continue;
      }
      printf(“%d\n”, query(root[lf – 1], root[rt], 1, 1000, h));
    }
  }

}

 

BZOJ 1146: [CTSC2008]网络管理Network

树上路径第k大
二分第k大是哪个再check有几个大于mid的即可~
这题就是传说中的只能用树链剖分而不能用动态树做的题!!!
[好像是一个模板题么 = =]
写了快400行的代码 (好吧我写得真心za….)
看到网上某犇随便虐了个130行代码水过瞬间就跪烂了。。。。。
另。我们机房的电脑是有多慢。。。
跑第三个点就要16s+ 跑所有点差不多150s
在八中跑所有点才用了10s+!!!
<以后一定不能相信机房电脑的运行速度= =>
————————–code————————————

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int maxn = 100005;
struct point
{
  int sum, fa, id, deep, hav, v;
}a[maxn];
struct line
{
  int to, next;
}li[maxn * 2];
struct seg_tree
{
  int root, fa, n;
}st[maxn * 8];
struct seg_node
{
  int l, r, lf, rt, root;
}sn[maxn * 8];
struct splay_node
{
  int l, r, fa, sum, v, faa;
}t[maxn * 15];
int n, q, l, be[maxn], n_lt, n_st, n_sn, n_spn, tt[maxn], m;
void makeline(int fr, int to)
{
  l++;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}
int makesplaytree(int v, int faa)
{
  n_spn++;
  t[n_spn].sum = 1;
  t[n_spn].v = v;
  t[n_spn].faa = faa;
  return n_spn;
}
void left(int now)
{
  int fa = t[now].fa;
  t[now].fa = t[fa].fa;
  if (t[t[fa].fa].l == fa) t[t[fa].fa].l = now;
  if (t[t[fa].fa].r == fa) t[t[fa].fa].r = now;
  t[fa].r = t[now].l;
  t[t[now].l].fa = fa;
  t[now].l = fa;
  t[fa].fa = now;
  t[fa].sum = t[t[fa].l].sum + t[t[fa].r].sum + 1;
  t[now].sum = t[t[now].l].sum + t[t[now].r].sum + 1;
}
void right(int now)
{
  int fa = t[now].fa;
  t[now].fa = t[fa].fa;
  if (t[t[fa].fa].l == fa) t[t[fa].fa].l = now;
  if (t[t[fa].fa].r == fa) t[t[fa].fa].r = now;
  t[fa].l = t[now].r;
  t[t[now].r].fa = fa;
  t[now].r = fa;
  t[fa].fa = now;
  t[fa].sum = t[t[fa].l].sum + t[t[fa].r].sum + 1;
  t[now].sum = t[t[now].l].sum + t[t[now].r].sum + 1;
}
void splay(int now, int ffa)
{
  while (t[now].fa != ffa)
  {
    int fa = t[now].fa;
    if (t[fa].fa == ffa)
      if (t[fa].l == now) right(now);
      else left(now);
    else
      if (t[t[fa].fa].l == fa)
        if (t[fa].l == now) right(fa), right(now);
        else left(now), right(now);
      else
        if (t[fa].l == now) right(now), left(now);
        else left(fa), left(now);
  }
  if (t[now].fa == 0) sn[t[now].faa].root = now;
}
void inssplaynode(int root, int v, int faa)
{
  n_spn++;
  int now = n_spn;
  t[now].sum = 1;
  t[now].v = v;
  t[now].faa = faa;
  while (true)
  {
    t[root].sum++;
    if (v <= t[root].v)
    {
      if (t[root].l) root = t[root].l;
      else
      {
        t[root].l = now;
        t[now].fa = root;
        break;
      }
    }
    else
    {
      if (t[root].r) root = t[root].r;
      else
      {
        t[root].r = now;
        t[now].fa = root;
        break;
      }
    }
  }
  splay(now, 0);
}
int mksegtree(int l, int r)
{
  n_sn++;
  int now = n_sn;
  sn[now].l = l;
  sn[now].r = r;
  if (l == r)
  {
    sn[now].root = makesplaytree(tt[l], now);
    return now;
  }
  int mid = (l + r) / 2;
  sn[now].lf = mksegtree(l, mid);
  sn[now].rt = mksegtree(mid + 1, r);
  sn[now].root = makesplaytree(tt[l], now);
  for (int i = l + 1; i <= r; i++) inssplaynode(sn[now].root, tt[i], now);
  return now;
}
void makesegtree(int now)
{
  m = 1;
  n_st++;
  st[n_st].fa = now;
  while (now)
  {
    tt[m++] = a[now].v;
    a[now].id = n_st;
    now = a[now].hav;
  }
  m -= 1;
  st[n_st].n = m;
  st[n_st].root = mksegtree(1, m);
}
void makerealtree(int now, int fa, int d)
{
  a[now].fa = fa;
  a[now].sum = 1;
  a[now].deep = d;
  int mx = 0, k = 0;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (to == fa) continue;
    makerealtree(to, now, d + 1);
    a[now].sum += a[to].sum;
    if (a[to].sum > mx)
    {
      if (k) makesegtree(k);
      mx = a[to].sum;
      k = to;
    }
    else makesegtree(to);
  }
  a[now].hav = k;
}
int lca(int fr, int to)
{
  while (a[fr].id != a[to].id)
  {
    if (a[st[a[fr].id].fa].deep < a[st[a[to].id].fa].deep) swap(fr, to);
    fr = a[st[a[fr].id].fa].fa;
  }
  return a[fr].deep < a[to].deep ? fr : to;
}
int getnum(int fr, int to)
{
  int t = lca(fr, to);
  return a[to].deep + a[fr].deep – a[t].deep * 2 + 1;
}
int querysplay(int now, int k)
{
  int ans = 0;
  while (now)
  {
    if (t[now].v >= k) now = t[now].l;
    else
    {
      ans += t[t[now].l].sum + 1;
      now = t[now].r;
    }
  }
  return ans;
}
int get(int now, int l, int r, int k)
{
  if (sn[now].l >= l && sn[now].r <= r) return querysplay(sn[now].root, k);
  int mid = (sn[now].l + sn[now].r) / 2;
  int ans = 0;
  if (l <= mid) ans += get(sn[now].lf, l, r, k);
  if (r >= mid + 1) ans += get(sn[now].rt, l, r, k);
  return ans;
}
int check(int fr, int to, int k)
{
  int ans = 0;
  while (a[fr].id != a[to].id)
  {
    if (a[st[a[fr].id].fa].deep < a[st[a[to].id].fa].deep) swap(fr, to);
    ans += get(st[a[fr].id].root, 1, a[fr].deep – a[st[a[fr].id].fa].deep + 1, k);
    fr = a[st[a[fr].id].fa].fa;
  }
  if (a[fr].deep < a[to].deep) swap(fr, to);
  return ans + get(st[a[fr].id].root, a[to].deep – a[st[a[fr].id].fa].deep + 1, a[fr].deep – a[st[a[fr].id].fa].deep + 1, k);
}
int query(int fr, int to, int k)
{
  int l = 0;
  int r = 100000001;
  while (l + 1 < r)
  {
    int mid = (l + r) / 2;
    if (check(fr, to, mid) >= k) r = mid;
    else l = mid;
  }
  return l;
}
int findsmaller(int now)
{
  now = t[now].l;
  while (t[now].r) now = t[now].r;
  return now;
}
int findbigger(int now)
{
  now = t[now].r;
  while (t[now].l) now = t[now].l;
  return now;
}
void splaych(int now, int fr, int to, int faa)
{
  while (now)
  {
    if (t[now].v == fr) break;
    if (t[now].v < fr) now = t[now].r;
    else now = t[now].l;
  }
  splay(now, 0);
  if (!t[now].l && !t[now].r)
  {
    t[now].v = to;
    return;
  }
  if (!t[now].l)
  {
    sn[faa].root = t[now].r;
    t[t[now].r].fa = 0;
  }
  else
  if (!t[now].r)
  {
    sn[faa].root = t[now].l;
    t[t[now].l].fa = 0;
  }
  else
  {
    int t1 = findsmaller(now);
    int t2 = findbigger(now);
    splay(t1, 0);
    splay(t2, t1);
    t[t2].l = 0;
    t[t2].sum–;
    t[t1].sum–;
  }
  inssplaynode(sn[faa].root, to, faa);
}
void segch(int now, int lr, int fr, int to)
{
  splaych(sn[now].root, fr, to, now);
  if (sn[now].l == sn[now].r) return;
  int mid = (sn[now].l + sn[now].r) / 2;
  if (lr <= mid) segch(sn[now].lf, lr, fr, to);
  else segch(sn[now].rt, lr, fr, to);
}
void change(int now, int k)
{
  segch(st[a[now].id].root, a[now].deep – a[st[a[now].id].fa].deep + 1, a[now].v, k);
  a[now].v = k;
}
int main()
{
  int test;
  scanf(“%d%d”, &n, &test);
  for (int i = 1; i <= n; i++) scanf(“%d”, &a[i].v);
  for (int i = 1; i < n; i++)
  {
    int fr, to;
    scanf(“%d%d”, &fr, &to);
    makeline(fr, to);
    makeline(to, fr);
  }
  makerealtree(1, 0, 1);
  makesegtree(1);
  for (int i = 0; i < test; i++)
  {
    int k, fr, to;
    scanf(“%d%d%d”, &k, &fr, &to);
    if (!k) change(fr, to);
    else
    {
      int t = getnum(fr, to);
      if (t < k) printf(“invalid request!\n”);
      else printf(“%d\n”, query(fr, to, t – k + 1));
    }
  }

}