数据结构

int n, c[N];

int lowbit(int x){return x & -x;}

void modify(int x, int val){
    for (; x <= n; x += lowbit(x)) c[x] += val;
}

ll query(int x){ //[1, x]
    ll res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

struct info{

};

struct tag{

};

info operator+(const info &l, const info &r){

}

info operator+(const info &v, const tag &t){ // 区间修改

}

tag operator+(const tag &t1, const tag &t2){ //懒标记和并

}

struct Node{
    tag t;
    info val;
} seg[N * 4];

void settag(int id, tag t){
    seg[id].val = seg[id].val + t;
    seg[id].t = seg[id].t + t;
}

void pushdown(int id){ // 每一步都需要标记下传
    if (){ // 标记非空
        settag(id * 2, seg[id].t);
        settag(id * 2 + 1, seg[id].t);
        //初始化标记

    }
}

void update(int id){
    seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}

void build(int id, int l, int r){
    if (l == r)
    {
        seg[id].val = info();
        seg[id].t = tag();
    }
    else
    {
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        update(id);
    }
}

info query(int id, int l, int r, int ql, int qr){
    if (l == ql && r == qr)
    {
        return seg[id].val;
    }
    int mid = (l + r) / 2;
    pushdown(id);
    if (qr <= mid)
        return query(id * 2, l, mid, ql, qr);
    else if (ql > mid)
        return query(id * 2 + 1, mid + 1, r, ql, qr);
    else
        return query(id * 2, l, mid, ql, mid) +
               query(id * 2 + 1, mid + 1, r, mid + 1, qr);
}

void modify(int id, int l, int r, int ql, int qr, tag t){
    if (l == ql && r == qr)
    {
        settag(id, t);
        return;
    }
    int mid = (l + r) / 2;
    pushdown(id);
    if (qr <= mid)
        modify(id * 2, l, mid, ql, qr, t);
    else if (ql > mid)
        modify(id * 2 + 1, mid + 1, r, ql, qr, t);
    else
    {
        modify(id * 2, l, mid, ql, mid, t);
        modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
    }
    update(id);
}

int nxt[N][M], cnt = 0;

void solve(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        string s;
        cin >> s;
        int len = s.size();
        int now = 0;
        for (int j = 0; j < len; j ++ ){
            int x = s[j] - 'a';
            if (!nxt[now][x]){
                nxt[now][x] = ++ cnt;
            }
            now = nxt[now][x];
        }
    }
}

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
using u64 = unsigned long long ;

const int V = 1e6;

u64 val[V + 1];

void solve() {
    for (int i = 1; i <= V; i ++ ){
        val[i] = rng();
    }
}

    pre[i] = pre[i - 1] ^ a;
    //判断 pre[--l] = pre[r]

    pre[i] = pre[i] + a;
    //判断pa[r] - pa[--l] == pb[r] - pb[--l]