CCPC2021桂林B

蒟蒻调了一天了，一直WA3, 有没有大佬帮忙康康。

#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
#define int long long
const int INF = 1e9; 

template <class T>
inline void read(T& a){  
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ;
}

int n, Q; 
char s1[N], s2[N]; 
int a[N][4];

struct Segment_tree{
  struct node{
    int w; 
    int col;   // 表示把某个区间全部刷成 col
    int siz; 

    node(){this->col = -1; return ; }
  } t[N << 2];  

  #define lson (o<<1)
  #define rson (o<<1|1)

  inline void pushup(int o){
    t[o].w = t[lson].w + t[rson].w;
    return ; 
  }

  inline void pushdown(int o, int l, int r){
    int mid = l + r >> 1; 
    if(t[o].col == -1) return ; 

    t[lson].col = t[o].col;
    t[rson].col = t[o].col; 

    t[lson].w = t[o].col * (mid - l + 1);
    t[rson].w = t[o].col * (r - mid); 
      
    t[o].col = -1;
    return ; 
  }

  void build(int o, int l, int r){
    t[o].siz = r - l + 1; 
    t[o].col = -1; 
    if(l == r){
      t[o].w = a[l][2]; 
      return ; 
    }
    int mid = l + r >> 1; 
    build(lson, l, mid); build(rson, mid + 1, r);
    pushup(o);
    return ; 
  }

  int query_he(int o, int l, int r, int in, int end){
    if(l > end || r < in) return 0; 
    if(l >= in && r <= end) return t[o].w; 
    int mid = l + r >> 1;
    pushdown(o, l, r); 
    return query_he(lson, l, mid, in, end) + query_he(rson, mid + 1, r, in, end); 
  }

  int query(int o, int l, int r, int in, int end, int k){ // 返回从 in 开始连续一串为 k 的最右端
    if(l > end || r < in) return -INF; 
    if(l == r){
      if(t[o].w == k) return l; 
      else return -INF; 
    }
    pushdown(o, l, r); 
    int mid = l + r >> 1;
    if(mid >= in){
      int W = query_he(1, 1, n, in, mid); 
      if(W == k * (mid - in + 1)) return max(mid, query(rson, mid + 1, r, in, end, k));
      else return query(lson, l, mid, in, end, k); 
    }
    else{
      return query(rson, mid + 1, r, in, end, k); 
    }
  }

  void update(int o, int l, int r, int in, int end, int k){
    if(l > end || r < in) return ; 
    if(l >= in && r <= end){
      t[o].w = k * (r - l + 1); 
      t[o].col = k; 
      return ; 
    }
    int mid = l + r >> 1;
    pushdown(o, l, r); 
    update(lson, l, mid, in, end, k);
    update(rson, mid + 1, r, in, end, k);
    pushup(o);
    return ; 
  }

  void print(int o, int l, int r){
    if(l == r){
      printf("%d", t[o].w);
      return ; 
    }
    int mid = l + r >> 1;
    pushdown(o, l, r);
    print(lson, l, mid);
    print(rson, mid + 1, r); 
    pushup(o); 
    return ; 
  }

} tree; 

signed main(){
  // freopen("hh.txt", "r", stdin); 
  read(n), read(Q);
  scanf("%s", s1 + 1);
  scanf("%s", s2 + 1); 
  for(int i = 1; i <= n; i++)
    a[n-i+1][0] = s1[i] - '0';
  for(int i = 1; i <= n; i++)
    a[n-i+1][1] = s2[i] - '0';
  for(int i = 1; i <= n; i++){
    a[i][2] += a[i][0] + a[i][1]; 
    while(a[i][2] >= 10){
      a[i+1][2] += a[i][2]/ 10; 
      a[i][2] %= 10; 
    }

  }

  tree.build(1, 1, n);  // 按照第三个数建

  /*下面有问题-----------------------------*/
  tree.print(1, 1, n); printf("\n"); 

  while(Q--){
    int opt, p, d; 
    read(opt), read(p), read(d); 
    opt--;
    p = n - p + 1; 

    int ans; 

    if(a[p][opt] == d){
      ans = 0;  
    }
    else{
      int ori = tree.query_he(1, 1, n, p, p); 
     
      bool jin = 0;
      if(a[p][opt] + a[p][opt^1] > ori) jin = 1; 
      ori -= a[p][opt]; 
      while(ori < 0) ori += 10;  // 得到不加上这一位的原始数字（包括后一位的进位）
      // printf("jin: %d\n", jin);  
      if(jin){ // 如果原来进位
        if(d + ori >= 10){ // 现在也进位， 那就后面的不用变
         tree.update(1, 1, n, p, p, (ori + d) % 10);        
         ans = 2; 
        }
        else{
         int lr = tree.query(1, 1, n, p + 1, n, 0);
         lr = max(lr, p);  
        //  printf("lr: %d\n", lr); 
         tree.update(1, 1, n, p, p, (ori + d) % 10); 
         tree.update(1, 1, n, p + 1, lr, 9);
         tree.update(1, 1, n, lr + 1, lr + 1, (tree.query_he(1, 1, n, lr + 1, lr + 1) - 1) % 10);
        //  printf("%d\n", 2 + min(lr, n) - p); 
          ans = 2 + min(lr, n) - p; 
          if(lr + 1 <= n) ans++; 
        }
     }
      else{  //如果原来不进位
       if(d + ori < 10){ // 现在也不进位
         tree.update(1, 1, n, p, p, (ori + d) % 10); 
        //  puts("2"); 
          ans = 2; 
       }
         else {
           int lr = tree.query(1, 1, n, p + 1, n, 9); 
          //  printf("lr: %d\n", lr); 
           lr = max(lr, p); 
           tree.update(1, 1, n, p, p, (ori + d) % 10);
           tree.update(1, 1, n, p + 1, lr, 0); 
           tree.update(1, 1, n, lr + 1, lr + 1, (tree.query_he(1, 1, n, lr + 1, lr + 1) + 1) % 10); 
            // printf("%d\n", 2 + min(lr, n) - p); 
            ans = 2 + min(lr, n) - p;
            if(lr + 1 <= n) ans++;  
          }
      }
    }
    tree.print(1, 1, n);  cout << endl; 
    printf("%lld %lld\n", tree.query_he(1, 1, n, p, p) % 10, ans); 
    a[p][opt] = d; 
  }
  return 0;
}