谁能帮帮卡卡常让我A!!!
查看原帖
谁能帮帮卡卡常让我A!!!
722677
iamputin楼主2024/11/22 16:22

T了3个点, 我看题解貌似有一篇和我思路一样的过掉了?

求大佬帮忙卡下常

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

namespace IO {
const char *ln = "\n";
const int str = 1 << 20;
struct IN {
  char buf[str], *s, *t;
  bool _;
  IN() : s(buf), t(buf), _(0) {}
  inline char gc() {
    return s == t && ((t = (s = buf) + fread(buf, 1, str, stdin)) == s)
               ? EOF
               : (*s++);
  }
  IN &operator>>(string &ch) {
    if (_)
      return *this;
    char c;
    while ((c = gc()) != EOF && isspace(c))
      ;
    if (c == EOF)
      return _ = 1, *this;
    ch += c;
    while ((c = gc()) != EOF && !isspace(c))
      ch += c;
    if (c == EOF)
      _ = 1;
    return *this;
  }
  template <typename T> IN &operator>>(T &x) {
    if (_)
      return *this;
    char c = gc();
    bool ff = 0;
    while (c != EOF && (c < '0' || c > '9'))
      ff ^= (c == '-'), c = gc();
    if (c == EOF) {
      _ = 1;
      return *this;
    }
    x = 0;
    while (c != EOF && '0' <= c && c <= '9')
      x = (x << 3) + (x << 1) + c - 48, c = gc();
    if (c == EOF)
      _ = 1;
    if (ff)
      x = -x;
    return *this;
  }
} in;
}

#define lowbit(x) (x & -x)

int n, m, q;

struct Tree {
  int t[MAXN];

  void add(int x) {
    for (; x <= m; x += lowbit(x))
      t[x]++;
  }
  void dec(int x) {
    for (; x <= m; x += lowbit(x))
      t[x]--;
  }

  int query(int x) {
    int res = 0;
    for (; x > 0; x -= lowbit(x))
      res += t[x];
    return res;
  }
} tree[30], wen_tree[30];
using namespace IO;
string source[MAXN];

signed main() {
  in >> n >> m >> q;

  for (int i = 1; i <= m; ++i) {
    in >> source[i];
    for (int j = 0; j < n; ++j) {
      if (source[i][j] == '1') {
        tree[j].add(i);
      } else if (source[i][j] == '?') {
        wen_tree[j].add(i);
      }
    }
  }
  unsigned int ans = 0;
  while (q--) {
    int opt;
    in >> opt;
    if (opt == 0) {
      int l, r;
      in >> l >> r;
      int len = r - l + 1;
      unsigned int ans1 = 1;
      for (int i = 0; i < n; ++i) {
        int a = tree[i].query(r) - tree[i].query(l - 1);
        int b = wen_tree[i].query(r) - wen_tree[i].query(l - 1),
            c = len - a - b;
        if (b == len) {
					ans1 <<= 1;
        } else if (a && c) {
					ans1 = 0;
          break;
        }
      }
			ans ^= ans1;
    } else {
      int pos;
      string t;
      in >> pos >> t;
      for (int i = 0; i < n; ++i) {
				if (source[pos][i] == '?') wen_tree[i].dec(pos);
				else if (source[pos][i] == '1') tree[i].dec(pos);
				if (t[i] == '?') wen_tree[i].add(pos);
				else if (t[i] == '1') tree[i].add(pos);
      }
      source[pos] = t;
    }
  }
  printf("%u", ans);
}
2024/11/22 16:22
加载中...