QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#858871#9774. Same SumbaoyangawaTL 6ms98776kbC++143.8kb2025-01-17 08:14:442025-01-17 08:14:45

Judging History

你现在查看的是最新测评结果

  • [2025-01-17 08:14:45]
  • 评测
  • 测评结果:TL
  • 用时:6ms
  • 内存:98776kb
  • [2025-01-17 08:14:44]
  • 提交

answer

#include <bits/stdc++.h>
#define frr(a) freopen(a, "r", stdin)
#define fww(a) freopen(a, "w", stdout)
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f, MB = 1 << 20;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct fio {
	char ib[MB + 100], *p, *q;
	fio() {
		p = q = ib;
	}
	char gc() {
		return getchar();
		if (p == q) {
			q = (p = ib) + fread(ib, 1, MB, stdin);
			if (p == q) return EOF;
		}
		return *p++;
	}
	template <typename T> void read(T& x) {
		char c = gc(), l = 0;
		x = 0;
		while (!isdigit(c)) l = c, c = gc();
		while ( isdigit(c)) x = (x << 1) + (x << 3) + c - 48, c = gc();
		if (l == '-') x = -x;
	}
	bool bk(char c) {
		return c == ' ' || c == '\r' || c == '\n' || c == '\t' || c == EOF;
	}
	void read(char& x) {
		char c = gc();
		while (bk(c)) c = gc();
		x = c;
	}
	void read(string& x) {
		char c = gc();
		x.clear();
		while ( bk(c)) c = gc();
		while (!bk(c)) x += c, c = gc();
	}
	template <typename T1, typename T2> void read(pair <T1, T2> &x) {
		read(x.fi), read(x.se);
	}
	template <typename T, typename ...Argc> void read(T& x, Argc&... argc) {
		read(x), read(argc...);
	}
	template <typename T> void readt(T bg, T ed) {
		for (T it = bg; it != ed; it++) {
			read(*it);
		}
	}
} IO;
const int N = 2e5 + 10;
int n, q;
ll a[N];
ll qpow(ll a, ll n, ll mod) {
	ll res = 1; n = (n % (mod - 1) + mod - 1) % (mod - 1);
	while (n) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod, n >>= 1;
	} return res;
}
struct seg {
	ll mod, B;
	struct node {
		ll V, I, mx, mn, ad;
		node (ll a = 0, ll b = 0, ll c = -INF, ll d = INF, ll e = 0) {
			V = a, I = b, mx = c, mn = d, ad = e;
		}
	} tr[4 * N];
	node merge(node a, node b) {
		return node((a.V + b.V) % mod, (a.I + b.I) % mod, max(a.mx, b.mx), min(a.mn, b.mn), 0);
	}
	void pushup(int x) {
		tr[x] = merge(tr[x << 1], tr[x << 1 | 1]);
	}
	void pushadd(int x, ll v) {
		tr[x].ad += v, tr[x].mx += v, tr[x].mn += v;
		tr[x].V = tr[x].V * qpow(B, v, mod) % mod, tr[x].I = tr[x].I * qpow(B, -v, mod) % mod;
	}
	void pushdown(int x) {
		ll &ad = tr[x].ad;
		if (ad) pushadd(x << 1, ad), pushadd(x << 1 | 1, ad), ad = 0;
	}
	void build(int x = 1, int L = 1, int R = n) {
		if (L == R) {
			tr[x] = node(qpow(B, a[L], mod), qpow(B, -a[L], mod), a[L], a[L], 0);
			return;
		} int mid = (L + R) >> 1; 
		build(x << 1, L, mid), build(x << 1 | 1, mid + 1, R);
		pushup(x);
	}
	void add(int l, int r, int v, int x = 1, int L = 1, int R = n) {
		if (l <= L && R <= r) return pushadd(x, v);
		pushdown(x); int mid = (L + R) >> 1;
		if (l <= mid) add(l, r, v, x << 1, L, mid);
		if (mid < r) add(l, r, v, x << 1 | 1, mid + 1, R);
		pushup(x);
	}
	node query(int l, int r, int x = 1, int L = 1, int R = n) {
		if (l <= L && R <= r) return tr[x];
		pushdown(x); int mid = (L + R) >> 1; node res;
		if (l <= mid) res = merge(res, query(l, r, x << 1, L, mid));
		if (mid < r) res = merge(res, query(l, r, x << 1 | 1, mid + 1, R));
		return res;
	}
	bool check(int l, int r) {
		node res = query(l, r);
		ll val = res.I * qpow(B, res.mx + res.mn, mod) % mod;
		return val == res.V;
	}
	void init(ll x, ll y) {
		mod = x, B = y;
		build();
	}
} T1, T2, T3;
void build() {
	T1.init(1e9 + 7, 131), T2.init(1e9 + 9, 13331), T3.init(998244353, 47);
}
void change(int l, int r, int v) {
	T1.add(l, r, v), T2.add(l, r, v), T3.add(l, r, v);
}
bool check(int l, int r) {
	return T1.check(l, r) && T2.check(l, r) && T3.check(l, r);
}
int main() {
	IO.read(n, q), IO.readt(a + 1, a + n + 1);
	build();
	while (q--) {
		int op, l, r; IO.read(op, l, r);
		if (op == 1) {
			int v; IO.read(v);
			change(l, r, v);
		} else {
			check(l, r) ? puts("YES") : puts("NO");
		}
	}
	return 0;
}
/*
8 4
1 2 3 4 5 6 7 8
2 1 8
1 1 4 4
2 1 6
2 1 8
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 98776kb

input:

8 4
1 2 3 4 5 6 7 8
2 1 8
1 1 4 4
2 1 6
2 1 8

output:

YES
NO
YES

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

score: -100
Time Limit Exceeded

input:

200000 200000
0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result: