### 题目描述

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

## 题目内容

$$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。

## 样例输入

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


## 样例输出

YES
YES
YES


## 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 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(){
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 | 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 | 1] = 1ll * add[x << 1 | 1] * mul[x] % M;
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;
mul[id] = 1ll * mul[id] * P % M;
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--) {
if (opr == 0){
update(1, 1, siz);
}else {
_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;
}