BZOJ 2789: [Poi2012]Letters

这题一定对于某个字母
一定是贪心的把离它最近的字母移过来
这样就可以对A串标出1~n的排列的一个序
对这个序求逆序对数即为ans

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
#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 = 1000005;

int be[26], b[maxn], n, next[maxn], a[maxn], t[maxn * 4];
char c1[maxn], c2[maxn];

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

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

int main()
{
  scanf("%d", &n);
  scanf("\n%s\n%s", c1, c2);
  for (int i = n - 1; i >= 0; --i)
    {
      int to = c2[i] - 'A';
      next[i] = be[to];
      be[to] = i;
    }
  for (int i = 0; i < n; ++i)
    a[i] = be[c1[i] - 'A'], be[c1[i] - 'A'] = next[be[c1[i] - 'A']];
  ll ans = 0;
  for (int i = n - 1; i >= 0; --i)
  {
    ans = ans + query(0, maxn, 1, a[i]);
    modify(0, maxn, 1, a[i]);
  }
  printf("%lld", ans);
}

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);
}

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));
    }
  }

}