afaasdfawerasdfasdf
查看原帖
afaasdfawerasdfasdf
390770
S0CRiA楼主2021/12/7 19:50

哪错了啊

#11对了其他都错了

//P3792 little Ynoi
#include <bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
typedef long long ll;

const int N = 5e5 + 10; const ll P = 1000000000000000009;
struct node{ int l, r; ll sum, mmin, mmax; } T[N*4];
int n, m; ll a[N];

void update(int p){
	T[p].mmin = min(T[lc].mmin, T[rc].mmin);
	T[p].mmax = max(T[lc].mmax, T[rc].mmax);
	T[p].sum = (T[lc].sum + T[rc].sum) % P;
}
void build(int p, int l, int r){
	T[p].l = l, T[p].r = r;
	if(l == r){
		T[p].mmin = T[p].mmax = a[l], T[p].sum = (ll)a[l] * a[l] % P;
	} else {
		int mid = l + r >> 1;
		build(lc, l, mid); build(rc, mid + 1, r);
		update(p);
	}
}
void modify(int p, int x, int y){
	if(T[p].l == T[p].r){
		T[p].mmin = T[p].mmax = y, T[p].sum = (ll)y * y % P;
	} else {
		int mid = T[p].l + T[p].r >> 1;
		if(x <= mid) modify(lc, x, y);
		else modify(rc, x, y);
		update(p);
	}
}
ll querymin(int p, int l, int r){
	if(l <= T[p].l && T[p].r <= r) return T[p].mmin;
	int mid = T[p].l + T[p].r >> 1; ll res = 0x3f3f3f3f3f3f3f3f;
	if(l <= mid) res = min(res, querymin(lc, l, mid));
	if(mid < r) res = min(res, querymin(rc, mid + 1, r));
	return res;
}
ll querymax(int p, int l, int r){
	if(l <= T[p].l && T[p].r <= r) return T[p].mmax;
	int mid = T[p].l + T[p].r >> 1; ll res = 0xcfcfcfcfcfcfcfcf;
	if(l <= mid) res = max(res, querymax(lc, l, mid));
	if(mid < r) res = max(res, querymax(rc, mid + 1, r));
	return res;
}
ll querysum(int p, int l, int r){
	if(l <= T[p].l && T[p].r <= r) return T[p].sum;
	int mid = T[p].l + T[p].r >> 1; ll res = 0;
	if(l <= mid) res = (res + querysum(lc, l, mid)) % P;
	if(mid < r) res = (res + querysum(rc, mid + 1, r)) % P;
	return res;
}
ll calc(ll l, ll r){
//	ll ans = 0; for(ll i = l; i <= r; ++ i) ans = (ans + i * i) % P;
//	return ans;
	return (r*(r+1)%P*((r+r+1)%P)%P - (l-1)*l%P*((l+l-1)%P)%P + P) % P;
}


int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++ i) scanf("%lld", &a[i]); build(1, 1, n);
	while(m--){
		int op, x, y; scanf("%d%d%d", &op, &x, &y);
		if(op == 1) modify(1, x, y);
		else {
			int l = querymin(1, x, y), r = querymax(1, x, y);
			if(r - l != y - x){ puts("yuanxing"); continue; }
			ll ans = calc((ll)l, (ll)r);
			if(ans == querysum(1, x, y) * 6 % P && r - l == y - x)
				puts("damushen"); else puts("yuanxing");
		}
	}
	return 0;
}
/*
5 1
100000001
100000002
100000003
100000004
100000005
2 1 5
*/
2021/12/7 19:50
加载中...