5pts 除 Sub1 全 RE 求调!
查看原帖
5pts 除 Sub1 全 RE 求调!
1296826
lcfollower楼主2025/2/2 23:47

rt,悬关 ×1\times 1

蒟蒻写了 nn(见题)棵线段树结果除了 Q=0Q = 0 都 RE 了 QwQ,有没有大佬帮我调一调?我去睡觉了。(

# include <bits/stdc++.h>

# define int long long
# define up(i ,x, y) for (int i = x ; i <= y; i ++)

using namespace std;

inline int read (){int s = 0 ; bool w = 0 ; char c = getchar () ; while (!isdigit (c)) {w |= (c == '-') ,c = getchar () ;} while (isdigit (c)){s = (s << 1) + (s << 3) + (c ^ 48) ; c = getchar ();}return w ? -s : s;}
inline void write (int x){if (x < 0) putchar ('-') ,x = -x; if (x > 9) write (x / 10) ; putchar (x % 10 | 48);}
inline void writesp (int x){write (x) ,putchar (' ');}
inline void writeln (int x){write (x) ,putchar ('\n');}

const int N = 1e5 + 8;

struct SGT {
  int l ,r ,s0 ,s63;
}tr[31][N << 2];

//tr[i][j] 第 i 个位置区间内的个数。

int n ,m ,Q ,result;
char ch[N][31];

inline void pushup (int u){
  up (i ,1, n) tr[i][u].s0 = tr[i][u << 1].s0 + tr[i][u << 1 | 1].s0 ,tr[i][u].s63 = tr[i][u << 1].s63 + tr[i][u << 1 | 1].s63;
} inline void build (int u ,int l ,int r){
  up (i ,1 ,n) tr[i][u].l = l ,tr[i][u].r = r; 

  if (l == r){
    up (i ,1 ,n)
      tr[i][u].s0 = (ch[l][i] == '0') ,tr[i][u].s63 = (ch[l][i] == '?');
    return ;
  }

  int mid = ((l + r) >> 1);

  build (u << 1 ,l ,mid);
  build (u << 1 | 1 ,mid + 1 ,r);

  pushup (u);

} inline void modify (int u ,int x ,string s){
  int l = tr[1][u].l ,r = tr[1][u].r;

  if (l == r && l == x){
    up (i ,1, n){
      if (s[i] == '1') continue;
      tr[i][u].s0 = max (tr[i][u].s0 - 1 ,0ll) ,tr[i][u].s63 = max (tr[i][u].s63 - 1, 0ll);
      tr[i][u].s0 += (s[i] == '0') ,tr[i][u].s63 += (s[i] == '?');
    }
    return ;
  }

  int mid = ((l + r) >> 1);

  if (x <= mid) modify (u << 1 ,x ,s);
  else modify (u << 1 | 1 ,x, s);

  pushup (u);

} inline int query0 (int i ,int u ,int L ,int R){
  int l = tr[i][u].l ,r = tr[i][u].r;

  if (l >= L && r <= R) return tr[i][u].s0;

  int mid = ((l + r) >> 1) ,res = 0;

  if (L <= mid) res += query0 (i ,u << 1 ,L ,R);

  if (mid < R) res += query0 (i ,u << 1 | 1 ,L ,R);
  
  return res;

} inline int query63 (int i ,int u ,int L ,int R){
  int l = tr[i][u].l ,r = tr[i][u].r;

  if (l >= L && r <= R) return tr[i][u].s63;

  int mid = ((l + r) >> 1) ,res = 0;

  if (L <= mid) res += query63 (i ,u << 1 ,L ,R);

  if (mid < R) res += query63 (i ,u << 1 | 1 ,L ,R);
  
  return res;

} signed main (){

  n = read () ,m = read () ,Q = read ();
//m 个 长度为 n 的字符串。

  up (i ,1 ,m) up (j ,1, n) cin >> ch[i][j];

  build (1 ,1 ,n);
//cout<<tr[1][1].s0<<endl;
  while (Q --){
    int op = read () ;

    if (!op){
      
      int l = read () ,r = read () ,ans = 1;
      bool f = 1;
      
      up (i ,1, n){
        int sum0 = query0 (i ,1 ,l ,r) ,sum63 = query63 (i ,1 ,l ,r);

        int len = (r - l + 1) - sum63;

//cout<<"len : " << len << endl;
//writesp (sum0) ,writeln (sum63);

        if (sum0 && sum0 != len) {f = 0 ; break;}

        if (!sum63) continue;

        if (sum63 == r - l + 1) ans *= 2;

      }
    
      if (!f) ans = 0;

      result ^= ans;

    } else {
      int pos = read () ;
      string s;
      cin >> s;
      s = ' ' + s;
      modify (1 ,pos ,s);
    }
  }

  writeln (result);
  return 0;

}
2025/2/2 23:47
加载中...