2019 年電子科技大學 ACM 暑期前集訓數據結構專題解題報告

https://acm.uestc.edu.cn/problem/fang-chai

(請先看 n題) 這題也是一道線段樹的題目,題目中的方差可以拆成和、平方和兩個數據來維護,這樣合併就很方便。而數據變化有加、乘、抹平兩種操作。根據乘法的分配率等定理,多次加乘最後可以化簡爲一次乘和一次加,爲避免出現分數,整合爲先乘後加比較方便。而抹平操作則可理解爲乘 0再加。這樣則有兩個標記。這題與 n題相比最關鍵的區別在於,該題先乘後加的二項式操作不具有結合律,須在更新下層元素之前 pushdown。

  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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1000000007;
inline ll M(ll n) { return (n + mod) % mod; }
int num[100000];
ll ans_sum, ans_s2;
struct tnode {//對節點需要賦初值、更新值、清除標記合併等操作,其中平方和的更新比 n題稍複雜,還有乘標記的默認值爲 1,標記的合併也值得注意。
  int l, r;
  ll sum, s2, mark1 = 1, mark2 = 0;
  inline tnode() {}
  inline tnode(int l, int r) {
    this->l = l, this->r = r;
    if (l == r) {
      this->sum = num[l - 1];
      this->s2 = M(this->sum * this->sum);
    }
  }
  void change(int multipie, int add) {
    this->s2 = M(M(this->s2 * M((ll)multipie * multipie)) +
                 2 * M(M((ll)add * multipie) * this->sum) +
                 M(M((ll)add * add) * this->len()));
    this->sum = M(this->sum * multipie + (ll)add * this->len());
    this->mark1 = M(this->mark1 * multipie);
    this->mark2 = M(this->mark2 * multipie + add);
  }
  inline void markdel() {
    this->mark1 = 1;
    this->mark2 = 0;
  }
  inline int mid() { return (this->l + this->r) >> 1; }
  inline void merge(tnode lc, tnode rc) {
    this->sum = M(lc.sum + rc.sum);
    this->s2 = M(lc.s2 + rc.s2);
  }
  inline int len() { return r - l + 1; }
};

tnode node[400000];
void buildtree(int l, int r, int pos = 1) {//由於特殊點都寫進了成員函數,後面按標準的線段樹寫就好
  tnode &n = node[pos];
  n = tnode(l, r);
  if (l == r) return;
  int lc = pos << 1, rc = pos << 1 | 1;
  buildtree(l, n.mid(), lc);
  buildtree(n.mid() + 1, r, rc);
  n.merge(node[lc], node[rc]);
}

inline void pushdown(int pos) {
  tnode &n = node[pos];
  node[pos << 1].change(n.mark1, n.mark2);
  node[pos << 1 | 1].change(n.mark1, n.mark2);
  n.markdel();
}

void query(int l, int r, int pos = 1) {
  tnode &n = node[pos];
  if (l > n.r || r < n.l) return;
  if (l <= n.l && r >= n.r) {
    ans_sum = M(ans_sum + n.sum);
    ans_s2 = M(ans_s2 + n.s2);
  } else {
    if (n.mark1 != 1 || n.mark2 != 0) pushdown(pos);
    query(l, r, pos << 1);
    query(l, r, pos << 1 | 1);
  }
}

void update(int op, int l, int r, int k, int pos = 1) {
  tnode &n = node[pos];
  if (l > n.r || r < n.l) return;
  if (l <= n.l && r >= n.r) switch (op) {//三種操作,加可以認爲是先乘 1,乘可以認爲加 0,抹平則是先乘 0
      case 1:
        n.change(1, k);
        break;
      case 2:
        n.change(k, 0);
        break;
      case 3:
        n.change(0, k);
    }
  else {
    int lc = pos << 1, rc = pos << 1 | 1;
    pushdown(pos);//更新子節點前先處理標記
    update(op, l, r, k, lc);
    update(op, l, r, k, rc);
    n.merge(node[lc], node[rc]);
  }
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; ++i) scanf("%d", num + i);
  buildtree(1, n);
  while (q--) {
    int op;
    int l, r;
    scanf("%d%d%d", &op, &l, &r);
    if (op == 4) {
      ans_sum = ans_s2 = 0;
      query(l, r);
      printf("%lld\n", M(ans_s2 * (r - l + 1) - M(ans_sum * ans_sum)));
    } else {
      int k;
      scanf("%d", &k);
      update(op, l, r, k);
    }
  }
}

B

https://acm.uestc.edu.cn/problem/tun-tu-liang

這是一道典型的 LCA,另外建樹部分使用鄰接表(鄰接矩陣內存爆炸,邊讀邊建樹想了很久也沒想到可行方法)。查閱一些資料後,本來對 Tarjan 比較有想法,但是寫代碼的時候出了一些問題,後來就去寫倍增了。

 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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct edge {
  int num, l;
};
list<edge> path[100001];
int dep[100001], U[100001][18], L[100001][18];
void buildtree(int pos = 1) {//根節點爲 1,從根開始對每個節點遍歷相鄰的邊,遇到未加入樹的就添加,並且遞歸操作。遍歷結束後 clear()釋放無用內存
  for (edge p : path[pos])
    if (!U[p.num][0]) {
      U[p.num][0] = pos;
      dep[p.num] = dep[pos] + 1;
      L[p.num][0] = p.l;
      buildtree(p.num);
    }
  path[pos].clear();
}
int find(int u, int v) {//核心思路就是類似於二分的方法,通過指數的變化逼近取值,將複雜度降到 O(logn)
  if (u == v) return 0;
  int ans = INT_MAX;
  if (dep[u] < dep[v]) swap(u, v);
  while (dep[u] - dep[v] > 1) {//把兩者的深度調至相同,由於有已知的深度差,通過對數計算確定跳的步數,理論上效率應該比像後面那樣從最大值開始循環略高
    int lo = log(dep[u] - dep[v]) / log(2);
    ans = min(ans, L[u][lo]), u = U[u][lo];
  }
  if (dep[u] != dep[v]) ans = min(ans, L[u][0]), u = U[u][0];
  if (u == v) return ans;
  for (int i = 17; i >= 0; --i) {//目標深度未知,只能循環判斷了
    if (i && U[u][i] == U[v][i]) {
      continue;
    }
    ans = min(ans, min(L[u][i], L[v][i]));
    u = U[u][i], v = U[v][i];
  }
  if (u == v) return ans;
  return min(ans, min(L[u][0], L[v][0]));
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    path[u].push_back({v, w});
    path[v].push_back({u, w});
  }
  U[1][0] = 1;//建樹前用鄰接表添加邊,並把根節點 1加入樹,
  buildtree();
  for (int i = 1; 1 << i < n; ++i)//遞推預處理
    for (int j = 1; j <= n; ++j)
      U[j][i] = U[U[j][i - 1]]
[i - 1],
      L[j][i] = min(L[j][i - 1], L[U[j][i - 1]]
[i - 1]);
  while (q--) {
    int u, v;
    scanf("%d%d", &u, &v);
    printf("%d\n", find(u, v));
  }
}

C

https://acm.uestc.edu.cn/problem/ren-zai-di-shang-zou-guo-cong-tian-shang-lai

這道題處理一條線段上面聯通塊的個數,並且是動態的。我們可以把各個聯通塊按順序排列起來,這樣查找更新都比較方便,而 set 容器很好地提供了排列和去重的功能,優先隊列雖然效率不錯但不提供刪除功能。

 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
#include <bits/stdc++.h>
using namespace std;
struct guo {//每個黑鍋的左右端點作爲一個節點
  int l, r;
  guo(int l, int r) { this->l = l, this->r = r; }
  bool operator<(guo ans) const { return this->r < ans.l; }//不加 const 過不了編譯,重載運算符。當 a<b、b<a 均爲假時,系統會認爲 a==b,因此只需重載一個比較運算符。
};
inline guo merge(guo a, guo b) { return guo(min(a.l, b.l), max(a.r, b.r)); }//合併兩個黑鍋
int main() {
  int n;
  scanf("%d", &n);
  set<guo> a;
  while (n--) {
    int l, r;
    scanf("%d%d", &l, &r);
    guo hei = guo(l, r);
    auto it = a.find(hei);
    while (it != a.end()) {//找到所有和新的黑鍋聯通的黑鍋,合併,刪除
      hei = merge(hei, *it);
      a.erase(it);
      it = a.find(hei);
    }
    a.insert(hei);
    printf("%lu", a.size());
    if (n) putchar(' ');
  }
}

D

https://acm.uestc.edu.cn/problem/mi-ma-1

這是我做的最憋屈的一題,因爲k==0的情況WA了十多次。。。好在最後善良的出題人在note裏給了提示。

首先這題中要求輸出各元素的相對位置不變,這符合隊列的性質,而同時又要求代表的十六進制值最大,所以使用單調隊列來解決這個問題。我在找到WA的原因之前,想了很久,改了不少次,折騰了很久。好像也可以線段樹,就是會多個log,也應該不會卡。

 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
#include <deque>
#include <iostream>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  int n, k;
  while (cin >> n >> k) {
    deque<char> nums;
    char tmp;
    if (!k) {//k 爲0 時直接讀完輸入進入下一組數據,最後 AC 的關鍵,其實 getline 可能更好,但是影響很小,所以不重交了
      while (n--) cin >> tmp;
      //這裏有無 cout<<endl;均可
      continue;
    }
    cin >> tmp;
    nums.push_front(tmp);
    for (int i = 0; i < n - k; ++i) {//前半部分直接按單調隊列的規則來
      cin >> tmp;
      while (!nums.empty() && nums.front() < tmp) nums.pop_front();
      nums.push_front(tmp);
    }
    for (int i = 1; i < k; ++i) {//後半部分一邊讀取新元素,一邊輸出並刪除最優元素,可確保個數足夠。把兩個循環拆開,常數應該比循環內加判斷小 1(其實是因爲我之前寫錯誤代碼的時候拆了,然後就不想改了)
      cout << nums.back();
      cin >> tmp;
      nums.pop_back();
      while (!nums.empty() && nums.front() < tmp) nums.pop_front();
    };
    cout << nums.back() << endl;//第二個循環少輸出了一個字符,現在補上,導致 k爲 0時也會輸出一個字符,從而 WA
  }
}

E

https://acm.uestc.edu.cn/problem/dong-ma-he-sha-tian-xia-di-yi/description

首先,任意個不同的數都可以構成一個單調序列,因此,這題實際上是要求區間中出現最多的數出現的次數,即區間衆數。區間衆數是一個很經典的難題,常見的做法有分塊、莫隊(離線)等等。這道題要用上一個詢問的答案來處理下一次詢問,因此離線做法不可行。

不管是那種做法,我們首先都可以把數列離散化一下,然後考慮分塊做法,把數列分爲$\sqrt{n}$大小的塊,然後我們可以求一個前綴和,即從第一塊到每一塊的每個元素的總出現次數,對每個塊都暴力遍歷一遍即可,$O(n\sqrt{n})$。然後再以塊爲單位枚舉起點和終點,從第i塊到第j塊的區間衆數要麼是從第i塊到第j-1塊的衆數,要麼就是出現在第j塊中的數,這樣利用前綴和可以在$O(\sqrt{n})$內求出每兩個塊的值,這樣複雜度爲$O((\sqrt{n})^2 \sqrt{n})$預處理就結束了,然後查詢就很方便,我們可以直接得到區間中整塊部分的衆數,再在兩端的不完整的塊中一個一個地暴力統計即可,複雜度也是$O(n\sqrt{n})$。

還有一些別的寫法,比如預處理各塊自己的衆數,然後用n個vector存各點的出現位置,然後用lowerbound差分找答案,這種寫法常數非常小,對於隨機數據比較快,但是複雜度多了一個$O(log(衆數出現次數))$,數據大量重複時就會很慢。

參考代碼:

 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
  #include <bits/stdc++.h>
  using namespace std;
  using ll = long long;
  #define RST(a) memset(a, 0, sizeof(a))
  #define RSTV(a, v) memset(a, v, sizeof(a))
  #define FOR(i, a, b) for (auto i = (a); i < (b); ++i)
  const int INF = 0x3f3f3f3f;
  int n, m, Size;
  int a[40001], pos[40001];
  int sum[201][40001];
  int res[201][201];
  int S[201];
  void init() {
    int bs = n / Size;
    FOR(i, 0, bs) {
      S[i] = Size;
      FOR(j, 0, Size * (i + 1))
      ++sum[i][a[j]];
    }
    if (n % Size) {
      S[bs] = n % Size;
      FOR(j, 0, n)
      ++sum[bs][a[j]];
    }
    FOR(i, 0, S[0])
    res[0][0] = max(res[0][0], sum[0][a[i]]);
    FOR(rblock, 1, bs) {
      res[0][rblock] = res[0][rblock - 1];
      FOR(i, rblock * Size, rblock * Size + S[rblock])
      res[0][rblock] = max(res[0][rblock], sum[rblock][a[i]]);
    }
    FOR(lblock, 1, bs) FOR(rblock, lblock, bs) {
      res[lblock][rblock] = res[lblock][rblock - 1];
      FOR(i, rblock * Size, rblock * Size + S[rblock])
      res[lblock][rblock] =
          max(res[lblock][rblock], sum[rblock][a[i]] - sum[lblock - 1][a[i]]);
    }
  }
  int in_int() {
    char c = getchar();
    int ans = 0;
    while (c > '9' || c < '0') c = getchar();
    while (c >= '0' && c <= '9') {
      ans = (ans << 3) + (ans << 1) + c - '0';
      c = getchar();
    }
    return ans;
  }
  int cnt[40001];
  int query(int l, int r) {
    RST(cnt);
    int maxc = 0;
    int lblock = l / Size, rblock = r / Size;
    if (lblock == rblock) FOR(i, l, r + 1) {
        ++cnt[a[i]];
        maxc = max(maxc, cnt[a[i]]);
      }
    else {
      // if (l % Size == 0) --lblock;
      // if ((r + 1) % Size == 0) ++rblock;
      FOR(i, l, Size * (lblock + 1)) {
        if (!cnt[a[i]]) cnt[a[i]] = sum[rblock - 1][a[i]] - sum[lblock][a[i]];
        ++cnt[a[i]];
        maxc = max(maxc, cnt[a[i]]);
      }
      FOR(i, Size * rblock, r + 1) {
        if (!cnt[a[i]]) cnt[a[i]] = sum[rblock - 1][a[i]] - sum[lblock][a[i]];
        ++cnt[a[i]];
        maxc = max(maxc, cnt[a[i]]);
      }
      if (lblock + 1 < rblock) maxc = max(maxc, res[lblock + 1][rblock - 1]);
    }
    return maxc;
  }
  int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    n = in_int();
    m = in_int();
    Size = sqrt(n);
    FOR(i, 0, n) a[i] = in_int();
    memcpy(pos, a, sizeof(int) * n);
    sort(pos, pos + n);
    auto lst = unique(pos, pos + n);
    FOR(i, 0, n) a[i] = lower_bound(pos, lst, a[i]) - pos;
    init();
    int result = 0;
    FOR(i, 0, m) {
      int l = in_int(), r = in_int();
      l = (l + result - 1) % n;
      r = (r + result - 1) % n;
      if (l > r) swap(l, r);
      printf("%d\n", result = query(l, r));
    }
  }

F

https://acm.uestc.edu.cn/problem/wo-yong-yuan-xi-huan-dong-ma-he-sha/description

這題在上題的基礎上,可以使用離線算法,但是對複雜度、常數的要求都較高。上題的思路無法滿足本題的要求,本題可以使用莫隊算法來解決問題。我們已知一個區間的狀態(各數出現的次數,衆數出現的次數,以及出現次數爲任意值的元素各有多少個),可以很快地得出其一個端點加一(或減一)後的狀態,根據增加或減少的數維護上面三個變量都是$O(1)$的。然後我們就要考慮一個順序,依次得到各個詢問的區間結果,而且複雜度較低。如果簡單地以主次關鍵字排序,次要的端點可能會反覆來回長距離移動,複雜度最壞可到$O(n^2)$。這裏我們可以對一個端點進行分塊,同一塊內的詢問按另一個端點排序,這樣該端點只會在$\sqrt{n}$範圍內來回移動(跨塊移動是單調的),另一個端點只會來回移動$\sqrt{n}$次,這樣即可保證複雜度爲$O(n\sqrt{n})$。

參考代碼:

 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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = (a); i < (b); ++i)
const int INF = 0x3f3f3f3f;

int n, m, Size;
int a[200001], pos[200001];
int in_int() {
  char c = getchar();
  int ans = 0;
  while (c > '9' || c < '0') c = getchar();
  while (c >= '0' && c <= '9') {
    ans = (ans << 3) + (ans << 1) + c - '0';
    c = getchar();
  }
  return ans;
}

int pp = 0, result[200001];
struct Q {
  int l, r, p, b;
  void get() {
    l = in_int() - 1;
    r = in_int() - 1;
    p = pp++;
    b = l / Size;
  }
  bool operator<(const Q& x) {
    return b ^ x.b ? b < x.b : b & 1 ? r > x.r : r < x.r;
  }
} query[200001];
int cnt[200001], sum[200001], res = 0;
inline void addr(int& R) {
  --sum[cnt[a[++R]]++];
  ++sum[cnt[a[R]]];
  res = max(res, cnt[a[R]]);
}
inline void eraser(int& R) {
  --sum[cnt[a[R]]];
  if (cnt[a[R]] == res && !sum[cnt[a[R]]]) --res;
  ++sum[--cnt[a[R--]]];
}
inline void addl(int& L) {
  --sum[cnt[a[--L]]++];
  ++sum[cnt[a[L]]];
  res = max(res, cnt[a[L]]);
}
inline void erasel(int& L) {
  --sum[cnt[a[L]]];
  if (cnt[a[L]] == res && !sum[cnt[a[L]]]) --res;
  ++sum[--cnt[a[L++]]];
}
void solve() {
  int L = 0, R = -1;
  FOR(i, 0, m) {
    auto& q = query[i];
    while (R < q.r) addr(R);
    while (L > q.l) addl(L);
    while (R > q.r) eraser(R);
    while (L < q.l) erasel(L);
    result[q.p] = res;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  n = in_int();
  m = in_int();
  Size = sqrt(n);
  FOR(i, 0, n) a[i] = in_int();
  memcpy(pos, a, sizeof(int) * n);
  sort(pos, pos + n);
  auto lst = unique(pos, pos + n);
  FOR(i, 0, n) a[i] = lower_bound(pos, lst, a[i]) - pos;
  FOR(i, 0, m) query[i].get();
  sort(query, query + m);
  solve();
  FOR(i, 0, m) printf("%d\n", result[i]);
}

G

https://acm.uestc.edu.cn/problem/pai-zhao

這題輸入時進行一遍求和預處理,然後就可以直接做差得子序列和,也可以判斷最優解也只需根據前綴和,可用單調隊列的思想找最優解,線性複雜度內解決問題(這題時限應該是有意沒卡暴力)。由於只需要一個最優值,所以可以直接把多餘的值pop(stl的priority_queue無此功能),保持隊列內元素的單調性,超出長度限制的元素也要pop掉。可以兩端pop的容器有list和deque,本來當時想由於不需要隨機訪問,用鏈表應該比較好的,但是對比了一下時間就打臉了。

(注:該方法也可以求矩形範圍的最值,對每行求一次,得到一個最值矩陣,再對其每列求一次即可,參考codeforces-1195E

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  long long sum[n + 1];
  for (int i = 1; i <= n; ++i) {//初始化求和,保留 sum[0],可以直接使用 sum[i]-sum[0]表示從第一個到第 i個的和,無需單獨加代碼
    scanf("%lld", &sum[i]);
    sum[i] += sum[i - 1];
  }
  deque<int> begin;
  long long result = LLONG_MIN;
  begin.push_front(0);
  for (int i = 1; i <= n; ++i) {
    int t = begin.size();//避免多次調用 begin.size(),講道理 deque 的size()複雜度爲 1,但是加了這句之後還是快了一丟丟
    while ( --t && sum[begin.front()] > sum[i]) begin.pop_front();//排出 sum 值大的元素,至少保留一個元素
    if (i - begin.back() > m) begin.pop_back();//如果長度超限,pop 末尾元素
    long long dsum = sum[i] - sum[begin.back()];
    if (dsum > result) result = dsum;//計算並更新最大值
    if (sum[begin.front()] > sum[i]) begin.pop_front();//在之前保留的元素和 i之間選擇下一步的最優解
    begin.push_front(i);
  }
  printf("%lld\n", result);
}

I

https://acm.uestc.edu.cn/problem/pai-ming

這是一個動態計算排名的題。各隊成績放數組裏就好,但是排名,在堆裏面反覆find隊1肯定複雜度肯定是過大的。不過,好在我們只關心隊1的名次,因此可以只排序成績比隊1好的隊伍,不斷增刪維護,使的隊1一直在排序的末尾,名次可直接用size讀取。STL中multiset是最合適的容器,priority_queue雖然更快但是功能不足。

 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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct T {//存儲過題數與罰時,重載運算符以比較成績
  ll pe = 0;
  int so = 0;
  inline void add(int n) { ++this->so, this->pe += n; }
  bool friend operator<(T a, T b) {
    return a.so == b.so ? a.pe < b.pe : a.so > b.so;
  }
};
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  T team[n + 1];
  multiset<T> trank;
  trank.insert(team[1]);//默認加入隊 1
  while (m--) {
    int t, p;
    scanf("%d%d", &t, &p);
    T tmp = team[t];
    team[t].add(p);
    auto itend = trank.end();
    if (t == 1) {
      auto it = trank.lower_bound(team[t]);
      do  trank.erase(it++);
      while (it != trank.end());//隊 1名次上升後,刪除後面的隊伍
      trank.insert(team[t]);
    } else if (team[t] < team[1]) {
      trank.insert(team[t]);
      if (tmp < team[1]) {
        trank.erase(trank.lower_bound(tmp));//刪除過期的數據
      }
    }
    printf("%lu\n", trank.size());
  }
}

J

https://acm.uestc.edu.cn/problem/chong-hai-dai

這題是在一個環中取互不相鄰的數,求其最大值。如果直接採用貪心的策略,取最大值a[tmp]後刪除a[tmp]、a[a[tmp].l]和a[a[tmp].r],則可能存在爲了一個最大的元素放棄兩個稍小元素的情況,並不能得到最優解。因此我們需要在貪心的過程中有“反悔”,選擇之前元素的兩個相鄰元素的機會。因此,我們可以加入a[a[tmp].l].value+a[a[tmp].r].value-a[tmp].value,下一次選擇該元素即相當於反悔選擇a[tmp],改爲選擇a[a[tmp].l]和a[a[tmp].r],按這個策略貪心,取完m元素求和即可。找最大值可以使用priority_queue。

 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
#include <bits/stdc++.h>
using namespace std;
const int visited = 10001;//取範圍外的值作爲已刪去的標記
struct node {
  int value, l, r;
  node() {}
  node(int value, int pos) {
    this->value = value;
    this->l = pos - 1, this->r = pos + 1;
  }
};
struct q {
  int value, pos;
  bool operator<(q m) const { return this->value < m.value; }
};//數組存儲各點的值和左右元素下標,隊列存儲值和對應的下標
int main() {
  int m, n;
  scanf("%d%d", &n, &m);
  if (n < m * 2) {//爲了取 m個不相鄰元素,至少需要 2 * m 個元素
    puts("Error!");
    return 0;
  }
  node a[n];
  priority_queue<q> pq;
  for (int i = 0; i < n; ++i) {
    int tmp;
    scanf("%d", &tmp);
    a[i] = node(tmp, i);
    pq.push({tmp, i});
  }
  a[0].l = n - 1, a[n - 1].r = 0;
  int ans = 0;
  while (m--) {
    q tmp;
    do {
      tmp = pq.top();
      pq.pop();
    } while (a[tmp.pos].value == visited);//在隊列中跳過已刪除的元素
    ans += tmp.value;
    tmp.value = a[tmp.pos].value =
        a[a[tmp.pos].l].value + a[a[tmp.pos].r].value - a[tmp.pos].value;
    pq.push(tmp);
    a[a[tmp.pos].l].value = a[a[tmp.pos].r].value = visited;
    a[tmp.pos].l = a[a[tmp.pos].l].l, a[tmp.pos].r = a[a[tmp.pos].r].r;
    a[a[tmp.pos].l].r = a[a[tmp.pos].r].l = tmp.pos;//刪除元素,調整相關元素的左右元素下標,形成新的環
  }
  printf("%d", ans);
}

K

https://acm.uestc.edu.cn/problem/dui-da-an

該題是在線地判斷一些數之間的關係是否矛盾,判斷條件爲奇偶。每個數有兩種可能,每行數據也對應兩種可能。對此可以把每個數的兩種可能作爲兩個點,顯然該兩點是矛盾的。然後根據每行數據成立的兩種可能,對並查集進行兩次連接操作,再檢查矛盾的兩點是否被連在同一個並查集中,如果在,則說明條件存在矛盾。

 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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000001;
int fa[2 * maxn];
int dep[2 * maxn];
//簡單的秩優化並查集
int find(int x) {
  if (fa[x] == x)
    return x;
  return fa[x] = find(fa[x]);
}
void connect(int x, int y) {//函數名 union 被stdc++.h 佔了。。
  x = find(x), y = find(y);
  if (dep[x] > dep[y])
    fa[y] = x;
  else {
    fa[x] = y;
    if (dep[x] == dep[y])
      ++dep[y];
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < 2 * maxn; ++i)//初始化父節點數組
    fa[i] = i;
  int i;
  for (i = 0; i < m; ++i) {
    int a, b;
    char l[5];
    scanf("%d%d%s", &a, &b, l);
    if (*l == 'e') {//判斷字符串,爲偶說明相同,同側相連即可,爲奇則兩側交叉相連。
      connect(a - 1, b);
      connect(a - 1 + maxn, b + maxn);
      if (find(a - 1) == find(a - 1 + maxn)) {
        printf("%d", i);
        return 0;
      }
    } else {
      connect(a - 1, b + maxn);
      connect(a - 1 + maxn, b);
      if (find(a - 1) == find(a - 1 + maxn)) {
        printf("%d", i);
        return 0;
      }
    }
  }
  puts("ORZQHQH");
}

L

https://acm.uestc.edu.cn/problem/wo-de-ti-mian-zui-jian-dan-kuai-lai-zuo

這題是一道比較複雜的線段樹題目。要求求最長等差數列的長度,既然是等差,我們就可以維護各數之間的差,這樣詢問區間l到r的最長等差序列長度,也就是詢問l+1到r的最長等值序列長度+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
104
#include <bits/stdc++.h>
using namespace std;
struct tnode {//除了最長相等序列長度之外,還要保存節點兩端的值以及兩端的相等序列長度,以便在合併時判斷兩邊的等值序列是否會相連形成更長的等值數列
  int l, r,  ll = 1, rl = 1, ml = 1;
  long long lv = 0, rv = 0, mark=0;
  inline tnode() {}
  inline tnode(int l, int r) { this->l = l, this->r = r; }
  inline void change(int add) {
    this->lv += add;
    this->rv += add;
    this->mark += (long long)add;
  }
  inline void markdel() { this->mark = 0; }
  inline int mid() { return (this->l + this->r) >> 1; }
  void merge(tnode lc, tnode rc) {//關鍵步驟,要考慮各種情況,確保得到的各變量正確(除了 l=1 的節點的左端點,因爲查詢時找的是 l+1 到r 的最長等值序列,不會涉及到該值)
    this->lv = lc.lv, this->rv = rc.rv;
    this->ll = lc.ll, this->rl = rc.rl;
    this->ml = max(lc.ml, rc.ml);
    if (lc.rv == rc.lv) {
      if (this->ml < lc.rl + rc.ll) this->ml = lc.rl + rc.ll;
      if (lc.len() == lc.ll) this->ll += rc.ll;
      if (rc.len() == rc.rl) this->rl += lc.rl;
    }
  }
  inline int len() { return r - l + 1; }
};

tnode node[400000];
tnode ans;
bool ans_add;
void buildtree(int l, int r, int pos = 1) {
  tnode &n = node[pos];
  n = tnode(l, r);
  if (l == r) return;
  int lc = pos << 1, rc = pos << 1 | 1;
  buildtree(l, n.mid(), lc);
  buildtree(n.mid() + 1, r, rc);
  n.merge(node[lc], node[rc]);
}

inline void pushdown(int pos) {
  tnode &n = node[pos];
  node[pos << 1].change(n.mark);
  node[pos << 1 | 1].change(n.mark);
  n.markdel();
}

void query(int l, int r, int pos = 1) {
  tnode &n = node[pos];
  int lc = pos << 1, rc = pos << 1 | 1;
  if (l > n.r || r < n.l) return;
  if (l <= n.l && r >= n.r) {//遞歸查找過程中左邊的點一定先被找到,所以可以把找到的第一個點存下來,後面找到的節點依次並上去,得到最終結果
    if (ans_add)
      ans.merge(ans, n);
    else {
      ans = n;
      ans_add = 1;
    }
  } else {
    if (n.mark) pushdown(pos);
    query(l, r, pos << 1);
    query(l, r, pos << 1 | 1);
  }
}

void update(int l, int r, int add, int pos = 1) {
  tnode &n = node[pos];
  if (l > n.r || r < n.l) return;
  if (l <= n.l && r >= n.r)
    n.change(add);
  else {
    int lc = pos << 1, rc = pos << 1 | 1;
    if (n.mark) pushdown(pos);
    update(l, r, add, lc);
    update(l, r, add, rc);
    n.merge(node[lc], node[rc]);
  }
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  buildtree(1, n);
  while (q--) {
    int op;
    int l, r;
    scanf("%d%d%d", &op, &l, &r);
    if (op) {
      if (l == r) {
        printf("1\n");
        continue;
      }
      ans_add = 0;//重置標記
      query(l + 1, r);
      printf("%d\n", ans.ml + 1);
    } else {//區間 l~r+1 會受到影響,各段受到的影響不同,爲了方便,分多次調用 update
      int a, k, p;
      scanf("%d%d%d", &a, &k, &p);
      update(l, l, a);
      if (p > l) update(l + 1, p, k);
      if (p < r) update(p + 1, r, -k);
      update(r + 1, r + 1, -a - (2 * p - l - r) * k);
    }
  }
}

N

https://acm.uestc.edu.cn/problem/shu-li-tong-ji

這題是最基本的帶標記線段樹,基本的加法操作,維護和與最值(極差爲最值之差)。由於基礎比較差,之前對基本的樹形結構都沒有動手完整地寫過,對遞歸和DFS的理解也不深。這次線段樹寫得非常難受。反覆看過很多教程,又重新仔細看了一下基本的二叉樹,踩了很多坑才動手把這題寫出來。

 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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll ans_sum, ans_max, ans_min;
struct tnode {//對於節點的基本操作:初始化,更新,刪除標記,合併等。出於方便還寫了區間長度和中點。延遲更新標記是比較一個有些抽象的概念,但是在優化複雜度的過程中不可或缺,當操作施加於整個區間時,由於加法完全滿足結合律,如果後面不會查詢到其子區間,就不用把更新往下傳,一組數據中往往大部分的節點更新都是可以不用傳到底的。但是如果查詢到子節點,就必須傳遞更新信息,否則結果將錯誤。於是在不知道是否會查詢子節點的情況下,暫時先保存更新信息,後面查詢的時候再按需傳遞更新
  ll l, r, sum = 0, max = 0, min = 0, mark = 0;
  inline tnode() {}
  inline tnode(ll l, ll r) { this->l = l, this->r = r; }
  inline tnode(ll sum, ll max, ll min) {
    this->sum = sum, this->max = max, this->min = min;
  }
  inline void add(ll add) {
    this->sum += add * (this->r - this->l + 1);
    this->max += add;
    this->min += add;
    this->mark += add;
  }
  inline void markdel() { this->mark = 0; }
  inline ll mid() { return (this->l + this->r) >> 1; }
  inline void merge(tnode lc, tnode rc) {
    this->sum = lc.sum + rc.sum + this->mark * (this->r - this->l + 1);
    this->max = std::max<ll>(lc.max, rc.max) + this->mark;
    this->min = std::min<ll>(lc.min, rc.min) + this->mark;
  }
};

tnode node[4000000];

inline void buildtree(ll l, ll r, ll pos = 1) {//遞歸建樹,以 1爲根節點
  tnode &n = node[pos];
  n = tnode(l, r);
  if (l == r) return;
  ll lc = pos << 1, rc = pos << 1 | 1;
  buildtree(l, n.mid(), lc);
  buildtree(n.mid() + 1, r, rc);
}

inline void pushdown(ll pos) {//把當前節點的標記推送到下層節點,然後清除標記,在查詢時調用
  tnode &n = node[pos];
  node[pos << 1].add(n.mark);
  node[pos << 1 | 1].add(n.mark);
  n.markdel();
}

void query(ll l, ll r, ll pos = 1) {//容易寫錯的一步。查詢操作,從大區間逐層向下遞歸,最終得出結果
  tnode &n = node[pos];
  if (l > n.r || r < n.l) return;
  if (l <= n.l && r >= n.r) {
    ans_sum += n.sum;
    ans_max = max<ll>(ans_max, n.max);
    ans_min = min<ll>(ans_min, n.min);
  } else {
    if (n.mark) pushdown(pos);
    query(l, r, pos << 1);
    query(l, r, pos << 1 | 1);
  }
}

void update(ll l, ll r, ll add, ll pos = 1) {//加法操作有結合律,更新時不需要 pushdown
  tnode &n = node[pos];
  if (l > n.r || r < n.l) return;
  if (l <= n.l && r >= n.r)
    n.add(add);
  else {
    ll lc = pos << 1, rc = pos << 1 | 1;
    update(l, r, add, lc);
    update(l, r, add, rc);
    n.merge(node[lc], node[rc]);
  }
}
int main() {
  ll n, q;
  scanf("%lld%lld", &n, &q);
  buildtree(1, n);
  while (q--) {
    int op;
    ll l, r;
    scanf("%d%lld%lld", &op, &l, &r);
    if (op == 1) {
      ll k;
      scanf("%lld", &k);
      update(l, r, k);
    } else {
      ans_sum = 0;
      ans_max = LLONG_MIN;
      ans_min = LLONG_MAX;
      query(l, r);
      if (op == 2)
        printf("%lld\n", ans_sum);
      else
        printf("%lld\n", ans_max - ans_min);
    }
  }
}

O

https://acm.uestc.edu.cn/problem/zhan-zheng

這是一個典型的用01字典樹解決抑或最值問題的題目。我們把所需的數字的二進制從高到低位地保存在字典樹中,查詢最值的時候根據貪心思想,即可輕鬆地找到最值。01字典樹可以是一棵二叉樹,但是這樣寫要佔用n個int的內存,超出了允許的範圍,因此我們只添加存在的節點

 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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int poi[30 * MAXN], ch[30 * MAXN][2], co[30 * MAXN][2], num = 0;//按照最大需求量開數組,另開一個數組記錄每個節點下數字的個數,還有一個數組記錄最後的節點對應的整個數字(這個數組不要也行,可在查詢函數中邊查邊算)
void insert(int x) {//插入數,從高到低
  int u = 0;
  for (int i = 29; i >= 0; --i) {
    int tmp = x >> i & 1;
    ++co[u][tmp];
    if (!ch[u][tmp]) {
      ch[u][tmp] = ++num;
    }
    u = ch[u][tmp];
  }
  poi[u] = x;
}

void erase(int x) {//這裏只操作記錄個數的數組,並以該數組作爲判斷是否有數的依據
  int u = 0;
  for (int i = 29; i >= 0; --i) {
    int tmp = x >> i & 1;
    --co[u][tmp];
    u = ch[u][tmp];
  }
}
int find_max(int x) {//貪心,優先不同值
  int u = 0;
  for (int i = 29; i >= 0; --i) {
    int tmp = x >> i & 1;
    if (co[u][tmp ^ 1])
      u = ch[u][tmp ^ 1];
    else
      u = ch[u][tmp];
  }
  return poi[u];
}
int find_min(int x) {//貪心,優先相同值
  int u = 0;
  for (int i = 29; i >= 0; --i) {
    int tmp = x >> i & 1;
    if (co[u][tmp])
      u = ch[u][tmp];
    else
      u = ch[u][tmp ^ 1];
  }
  return poi[u];
}
int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int o, v;
    scanf("%d%d", &o, &v);
    switch (o) {
      case 1:
        insert(v);
        break;
      case 2:
        erase(v);
        break;
      case 3:
        printf("%d %d\n", find_min(v) ^ v, find_max(v) ^ v);
    }
  }
}
0%