Skip to content

14237: 【原4237】Russian Link Up

题目

题目描述

author: Chen Yuxuan & Pikachu 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4237

时间限制:1s,空间限制:256MB

题目背景

某天,小Z同学带着同学去薰衣草公园玩。一路上他发现了一台奇怪的游戏机。游戏的规则是现在有\(n\)个桶,每个桶都可以从唯一的入口放入一些数字,现在有两个操作。一个是向某个区间内的筒子都放入数字\(p\)以及询问其中某两个桶子是不是的数字以及其顺序是否完全相同。小Z同学刚刚写完编译器想放松放松,但是又不想被一起出去玩的同学打败,请你帮助小Z同学解决这个问题。

由于题目背景有点复杂,贴心的助教帮你翻译成了计算机科学的版本。

题目内容

给出一个长度为\(n\)的序列\({a_1, a_2, a_3 \cdots a_n}\),其中序列的每个元素\(a_i\)都是一个线性表,支持以下两种操作并且给出线性表相等的定义:
操作1: 在线性表的尾部插入一个元素;
操作2: 清空整个线性表。
线性表相等:类似于字符串相等定义,即两个线性表长度相同,相同下标位置的数相等。
接下来有\(m\)个操作,每个操作都是以下两种操作中的一种:
\(0\ \ L \ \ R\ \ K\):对\(\forall i \in [L, R]\),在\(a_i\)的尾部插入元素K;
\(1\ \ X \ \ Y\):查询是否满足\(a_X == a_Y\),如果满足则输出YES,并且清空\(a_X, a_Y\);反之输出NO。

输入格式

第一行两个整数\(n\)和\(m\)。
第二行至\(m+1\)行,每一行为上述的操作。

输出格式

对于每个查询操作,输出一行结果,为YES或NO。

样例输入

10000 5
0 1 5000 52
0 5001 10000 52
1 929 993
1 3062 9189
1 7693 8580

样例输出

YES
YES
YES

提示

为了防止卡评测机,可以include头文件<cassert>,如果你的程序只能满足前30%,请在读入完n,m后加入语句assert(n <= 10 && m <= 10);。如果你的程序只能满足前60%,请在读入完n,m后加入语句assert(n <= 100 && m <= 100);。 反复提交同一个超时代码将认定为卡评测机。 注意输出的大小写

数据规模

对于30%的数据,\(2 \leq n \leq 10\),\(1 \leq m \leq 10\)。 对于60%的数据,\(2 \leq n \leq 100\),\(1 \leq m \leq 100\)。 对于100%的数据,\(2 \leq n \leq 2* 10^5\),\(1 \leq m \leq 2 * 10^5\),\(1 \leq L \leq R \leq n\),\(1 \leq K \leq 256;\),\(1 \leq X, Y \leq n\) ,\(X\neq Y\)。

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdio"
using namespace std;

class node {
public:
    //unsigned long long val=0;
    int left = 0, right = 0;
    unsigned long long tag = 0, tag_num = 0;
};

node smt[800009];
unsigned long long pnum[200009] = { 0 };

void build_tree(int l, int r, int root) {
    smt[root].left = l;
    smt[root].right = r;
    if (l == r - 1) {
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(l, mid, root * 2);
    build_tree(mid, r, root * 2 + 1);
}

void push_down(int root) {
    smt[root * 2].tag = (smt[root * 2].tag * pnum[smt[root].tag_num] + smt[root].tag);
    smt[root * 2].tag_num += smt[root].tag_num;
    smt[root * 2 + 1].tag = (smt[root * 2 + 1].tag * pnum[smt[root].tag_num] + smt[root].tag);
    smt[root * 2 + 1].tag_num += smt[root].tag_num;
    smt[root].tag = 0;
    smt[root].tag_num = 0;
}

void update(int l, int r, unsigned long long val, int root) {
    if (l <= smt[root].left && smt[root].right <= r) {
        smt[root].tag = smt[root].tag * (unsigned long long)257 + val;
        smt[root].tag_num++;
        return;
    }
    int mid = (smt[root].left + smt[root].right) >> 1;
    push_down(root);
    if (l < mid) {
        update(l, r, val, root * 2);
    }
    if (r > mid) {
        update(l, r, val, root * 2 + 1);
    }
}

unsigned long long query(int l, int r, int root) {
    if (l <= smt[root].left && smt[root].right <= r) {
        return smt[root].tag;
    }
    int mid = (smt[root].left + smt[root].right) >> 1;
    push_down(root);
    if (l < mid) {
        return query(l, r, root * 2);
    }
    if (r > mid) {
        return query(l, r, root * 2 + 1);
    }
}

int get_pos(int pos, int root) {
    if (smt[root].right - smt[root].left == 1) {
        return root;
    }
    int mid = (smt[root].right + smt[root].left) >> 1;
    if (pos < mid)
        return get_pos(pos, root * 2);
    else
        return get_pos(pos, root * 2 + 1);
}

int main() {
    pnum[0] = 1;
    for (int i = 1; i < 200000; ++i)
        pnum[i] = pnum[i - 1] * (unsigned long long)257;
    int n, m;
    scanf("%d %d", &n, &m);
    build_tree(0, n, 1);

    for (; m > 0; --m) {
        int op;
        scanf("%d", &op);

        if (op == 0) {
            int L, R, K;
            scanf("%d %d %d", &L, &R, &K);
            update(L - 1, R, K, 1);
        }
        else {
            int X, Y;
            scanf("%d %d", &X, &Y);
            auto a = query(X - 1, X, 1), b = query(Y - 1, Y, 1);
            if (a == b) {
                printf("YES\n");
                auto pos1 = get_pos(X - 1, 1), pos2 = get_pos(Y - 1, 1);
                smt[pos1].tag = 0;
                smt[pos2].tag = 0;
                smt[pos1].tag_num = 0;
                smt[pos2].tag_num = 0;
            }
            else {
                printf("NO\n");
            }
        }
    }

    return 0;
}

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4237.md
    Hint: use hash value to represent a sequence
*/
#include <cstdio>
#define INF 2000000000
#define M 1000000007
#define P 17171
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, seg[530000], mul[530000], add[530000];
int siz, _l, _r, _v;
inline int addmod(int x, int y){
    return (x + y >= M ? x + y - M: x + y);
}
void init(){
    n = read(), m = read();
    for (siz = 1; siz < n; siz <<= 1)
        ;
    for (int i = 1; i < (siz << 1); ++i)
        seg[i] = 0, mul[i] = 1, add[i] = 0;
}
void pushdown(int x){
    // if ((x << 1) > siz) return ;
    seg[x << 1] = 1ll * seg[x << 1] * mul[x] % M;
    seg[x << 1] = addmod(seg[x << 1], add[x]);
    seg[x << 1 | 1] = 1ll * seg[x << 1 | 1] * mul[x] % M;
    seg[x << 1 | 1] = addmod(seg[x << 1 | 1], add[x]);
    add[x << 1] = 1ll * add[x << 1] * mul[x] % M;
    add[x << 1] = addmod(add[x << 1], add[x]);
    add[x << 1 | 1] = 1ll * add[x << 1 | 1] * mul[x] % M;
    add[x << 1 | 1] = addmod(add[x << 1 | 1], add[x]);
    mul[x << 1] = 1ll * mul[x << 1] * mul[x] % M;
    mul[x << 1 | 1] = 1ll * mul[x << 1 | 1] * mul[x] % M;
    mul[x] = 1, add[x] = 0;
}
void update(int id, int l, int r){
    if (_l > r || _r < l) return ;
    if (_l <= l && _r >= r){
        seg[id] = 1ll * seg[id] * P % M;
        seg[id] = addmod(seg[id], _v);
        mul[id] = 1ll * mul[id] * P % M;
        add[id] = 1ll * add[id] * P % M;
        add[id] = addmod(add[id], _v);
        return ;
    }
    pushdown(id); 
    int mid = (l + r) >> 1;
    update(id << 1, l, mid);
    update(id << 1 | 1, mid + 1, r);
}
int query(int id, int l, int r){
    if (l > _r || r < _l) return 0;
    if (_l <= l && r <= _r) return seg[id];
    pushdown(id);
    int mid = (l + r) >> 1;
    return query(id << 1, l, mid) + query(id << 1 | 1, mid + 1, r);
}
void solve(){
    while (m--) {
        int opr = read();
        if (opr == 0){
            _l = read(), _r = read(), _v = read();
            update(1, 1, siz);  
        }else {
            int p1 = read(), p2 = read();
            _l = _r = p1;
            int t1 = query(1, 1, siz);
            _l = _r = p2;
            int t2 = query(1, 1, siz);
            if (t1 == t2) 
                printf("YES\n"), seg[p1 + siz - 1] = seg[p2 + siz - 1] = 0;
            else printf("NO\n");
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}