题目地址
题解
由乃题还是毒瘤啊orz
显然的一个结论是，如果保证不重复，维护区间min，max然后判断max-min+1==r-l+1是否成立即可
但是有重复
于是就要orz题解区的各位大佬了
各种神奇的判重方法是怎么想出来的qwq
这里列举几种
1.维护区间平方和+对大质数取模防止爆
这种我写了但是不知道为什么取模了就挂
2.维护区间平方和
直接暴力维护...然后就过了..？我写的就是这种
这里大概说一下：
就是维护一下区间min,max,平方和，这些线段树都可以做到
然后首先判断一下是否(max-min+1==r-l+1)
这是第一重判定
然后第二重判定用公式和实际平方和判
[sum{i^2}==sum(sum为区间平方和)
]
什么？你不知道公式？
(sum_{i=1}^{n}{i^2}=frac{n(n+1)(2n+1)}{6})
但是公式只有70。这样子乘会爆
于是我们暴力枚举求平方和
然后就过了
（虽然很慢就是了）
#include <bits/stdc++.h>
#define ll long long
const ll inf = 5e18;
const ll mod = 1e9 + 7;
const ll inv6 = 166666668;
#define il inline
namespace io {
#define in(a) a=read()
#define out(a) write(a)
#define outn(a) out(a),putchar('
')
#define I_int ll
inline I_int read() {
I_int x = 0 , f = 1 ; char c = getchar() ;
while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
return x * f ;
}
char F[ 200 ] ;
inline void write( I_int x ) {
if( x == 0 ) { putchar( '0' ) ; return ; }
I_int tmp = x > 0 ? x : -x ;
if( x < 0 ) putchar( '-' ) ;
int cnt = 0 ;
while( tmp > 0 ) {
F[ cnt ++ ] = tmp % 10 + '0' ;
tmp /= 10 ;
}
while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
}
#undef I_int
}
using namespace io ;
using namespace std ;
#define N 500010
int n, m;
ll a[N];
namespace seg_tree {
struct tree {
int l, r;
ll mx, mn;
ll sum;
} t[N << 2];
#define lc (rt << 1)
#define rc (rt << 1 | 1)
#define mid ((l + r) >> 1)
void pushup(int rt) {
t[rt].mn = min(t[lc].mn, t[rc].mn);
t[rt].mx = max(t[lc].mx, t[rc].mx);
t[rt].sum = (t[lc].sum + t[rc].sum);
}
void build(int l, int r, int rt) {
t[rt].l = l; t[rt].r = r; if(l == r) {t[rt].mn = t[rt].mx = a[l]; t[rt].sum = a[l]*a[l]; return;}
build(l, mid, lc); build(mid + 1, r, rc); pushup(rt);
}
#define l t[rt].l
#define r t[rt].r
void upd(int L, ll c, int rt) {
if(l == r) { t[rt].mn = t[rt].mx = c; t[rt].sum = c * c; return; }
if(L <= mid) upd(L, c, lc); if(L > mid) upd(L, c, rc); pushup(rt);
}
ll query1(int L, int R, int rt) { ll ans = 0; //平方和
if(L <= l && r <= R) return t[rt].sum;
if(L <= mid) ans = (ans + query1(L, R, lc)); if(R > mid) ans = (ans + query1(L, R, rc));
return ans;
}
ll query2(int L, int R, int rt) { ll ans = inf; //最小
if(L <= l && r <= R) return t[rt].mn;
if(L <= mid) ans = min(ans, query2(L, R, lc)); if(R > mid) ans = min(ans, query2(L, R, rc));
return ans;
}
ll query3(int L, int R, int rt) { ll ans = -inf; //最大
if(L <= l && r <= R) return t[rt].mx;
if(L <= mid) ans = max(ans, query3(L, R, lc)); if(R > mid) ans = max(ans, query3(L, R, rc));
return ans;
}
#undef l
#undef r
#undef mid
#undef lc
#undef rc
}using namespace seg_tree;
ll calc(ll l, ll r) {
ll ans = 0;
for(ll i = l; i <= r; i ++) {
ans = ans + i * i;
}
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
n = read(), m = read();
for(int i = 1; i <= n; i ++) a[i] = read();
build(1, n, 1);
for(int i = 1; i <= m; i ++) {
int opt = read(), l = read(), r = read();
if(opt == 1) upd(l, r, 1);
else {
ll mx = query3(l, r, 1), mn = query2(l, r, 1);
// printf("Case#%d:max=%lld,min=%lld
",i,mx,mn);
if(mx - mn != (r - l)) {puts("yuanxing"); continue;}
if(query1(l, r, 1) == calc(mn, mx)) puts("damushen");
else puts("yuanxing");
}
}
return 0;
}
3.平衡树+线段树
orz数据结构爷，不过貌似会爆空间
这里放个链接