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

(请先看 n题) 这题也是一道线段树的题目,题目中的方差可以拆成和、平方和两个数据来维护,这样合并就很方便。而数据变化有加、乘、抹平两种操作。根据乘法的分配率等定理,多次加乘最后可以化简为一次乘和一次加,为避免出现分数,整合为先乘后加比较方便。而抹平操作则可理解为乘 0再加。这样则有两个标记。这题与 n题相比最关键的区别在于,该题先乘后加的二项式操作不具有结合律,须在更新下层元素之前 pushdown。

#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 比较有想法,但是写代码的时候出了一些问题,后来就去写倍增了。

#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 容器很好地提供了排列和去重的功能,优先队列虽然效率不错但不提供删除功能。

#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,也应该不会卡。

#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(众数出现次数))$,数据大量重复时就会很慢。

参考代码:

  #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})$。

参考代码:

#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

#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虽然更快但是功能不足。

#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。

#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

该题是在线地判断一些数之间的关系是否矛盾,判断条件为奇偶。每个数有两种可能,每行数据也对应两种可能。对此可以把每个数的两种可能作为两个点,显然该两点是矛盾的。然后根据每行数据成立的两种可能,对并查集进行两次连接操作,再检查矛盾的两点是否被连在同一个并查集中,如果在,则说明条件存在矛盾。

#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。

#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的理解也不深。这次线段树写得非常难受。反复看过很多教程,又重新仔细看了一下基本的二叉树,踩了很多坑才动手把这题写出来。

#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的内存,超出了允许的范围,因此我们只添加存在的节点

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