佛山电商网站建设,wordpress 主题栏目修改,做网站都需要哪些软硬件,用网上的文章做网站行吗原题链接
题目大意 给定一个长度为 n 的非负整数序列 a #xff0c;初始时所有数字均被标记为蓝色#xff0c;youyou 和 yy 轮流对序列 a 进行操作#xff0c;由 youyou 开始。 • 如果当前是 youyou 的回合#xff0c;那么他可以至多选择连续的 c 1 个数…原题链接
题目大意 给定一个长度为 n 的非负整数序列 a 初始时所有数字均被标记为蓝色youyou 和 yy 轮流对序列 a 进行操作由 youyou 开始。 • 如果当前是 youyou 的回合那么他可以至多选择连续的 c 1 个数如果他们的和小于等于 w 1 则标记为红色。 • 如果当前是 yy 的回合那么他可以至多选择连续的 c 2 个数如果他们的和大于 w 2 则标记为蓝色。 定义 youyou 胜利即是在游戏任意时刻所有数字都被标记为红色定义 yy 胜利则是在无穷多个回合内 youyou 无法胜利。现在给定 q 个操作对于每个操作给定三个数 opt , x , y 。 • 如果 opt 为 1 表示将 a x 增加 y 。 • 如果 opt 为 2 表示在序列 [ x , y ] 上进行一轮游戏。 对于每一个操作 2 判断 youyou 能否获得胜利 解题思路 代码如下
#include bits/stdc.h
#define ll long longusing namespace std;const int maxn 3e5 5;int n, q, c1, c2;
ll w1, w2;
ll a[maxn], tr[maxn];void upd(int id, ll k){for(int i id; i n; i i -i) tr[i] k;
}
ll que(int id){ll s 0;for(int i id; i 0; i - i -i) s tr[i];return s;
}
namespace seg{
#define l(x) (x 1)
#define r(x) (x 1 | 1)
ll max1[maxn 2], tag[maxn 2];
void up(int x){max1[x] max(max1[l(x)], max1[r(x)]);
}
void down(int x){max1[l(x)] tag[x], tag[l(x)] tag[x];max1[r(x)] tag[x], tag[r(x)] tag[x];tag[x] 0;
}
void update(int x, int l, int r, int ql, int qr, ll k){if(ql l r qr){max1[x] k, tag[x] k;return;}down(x);int mid l r 1;if(ql mid) update(l(x), l, mid, ql, qr, k);if(qr mid) update(r(x), mid 1, r, ql, qr, k);up(x);
}
int query1(int x, int l, int r, int ql, int qr, ll k){if(ql l r qr){if(max1[x] k) return 0;if(l r){if(max1[x] k) return l;else return 0;}down(x);int mid l r 1;if(max1[l(x)] k) return query1(l(x), l, mid, ql, qr, k);else return query1(r(x), mid 1, r, ql, qr, k);}down(x);int mid l r 1, res 0;if(ql mid) res query1(l(x), l, mid, ql, qr, k);if(res) return res;if(qr mid) res query1(r(x), mid 1, r, ql, qr, k);return res;
}
int query2(int x, int l, int r, int ql, int qr, ll k){if(ql l r qr){if(max1[x] k) return 0;if(l r){if(max1[x] k) return l;else return 0;}down(x);int mid l r 1;if(max1[r(x)] k) return query2(r(x), mid 1, r, ql, qr, k);else return query2(l(x), l, mid, ql, qr, k);}down(x);int mid l r 1, res 0;if(qr mid) res query2(r(x), mid 1, r, ql, qr, k);if(res) return res;if(ql mid) res query2(l(x), l, mid, ql, qr, k);return res;
}}
namespace seg2{
#define l(x) (x 1)
#define r(x) (x 1 | 1)
ll max1[maxn 2];
void up(int x){max1[x] max(max1[l(x)], max1[r(x)]);
}
void build(int x, int l, int r){if(l r){max1[x] a[l];return;}int mid l r 1;build(l(x), l, mid), build(r(x), mid 1, r);up(x);
}
void update(int x, int l, int r, int id, ll k){if(l r){max1[x] k;return;}int mid l r 1;if(id mid) update(l(x), l, mid, id, k);else update(r(x), mid 1, r, id, k);up(x);
}
ll query(int x, int l, int r, int ql, int qr){if(ql l r qr) return max1[x];int mid l r 1;ll res 0;if(ql mid) res max(res, query(l(x), l, mid, ql, qr));if(qr mid) res max(res, query(r(x), mid 1, r, ql, qr));return res;
}}int main(){scanf(%d %d %d %d %lld %lld, n, q, c1, c2, w1, w2);for(int i 1; i n; i ) scanf(%lld, a[i]);for(int i 1; i n; i ){upd(i, a[i]);seg::update(1, 1, n, max(1, i - c2 1), i, a[i]);}seg2::build(1, 1, n);while(q --){int op;scanf(%d, op);if(op 1){int x;ll y;scanf(%d %lld, x, y);upd(x, y);seg::update(1, 1, n, max(1, x - c2 1), x, y);seg2::update(1, 1, n, x, y);a[x] y;}else{int l, r;scanf(%d %d, l, r);if(seg2::query(1, 1, n, l, r) w1){printf(tetris\n);continue;}int L 0, R 0;if(r - l 1 c2){if(que(r) - que(l - 1) w2) L l, R r;}else{L seg::query1(1, 1, n, l, r - c2 1, w2);R seg::query2(1, 1, n, l, r - c2 1, w2) c2 - 1;}if(!L || !R){printf(cont\n);continue;}if(que(R) - que(L - 1) w1 R - L 1 c1) printf(cont\n);else printf(tetris\n);}}return 0;
}
线段树树状数组做法80pts
#includebits/stdc.h
#define int long long
using namespace std;
const int MAXN3e65;
int n,q,c1,c2,w1,w2,a[MAXN],t[MAXN];
inline int read()
{int number0,Fd1;char chgetchar();while(ch0||ch9){if(ch-)Fd-1;chgetchar();}while(ch0ch9)number(number1)(number3)(ch^48),chgetchar();return number*Fd;
}
inline void write(int number)
{if(number0)putchar(-),number-number;if(number9)write(number/10);putchar(number%100);
}
struct Tree{int l,r,sum,laz;#define l(x) tree[x].l#define r(x) tree[x].r#define sum(x) tree[x].sum#define laz(x) tree[x].laz
}tree[MAXN1];
inline int Build(int p,int l,int r)
{l(p)l,r(p)r;if(lr)return sum(p)a[l];int midlr1;return sum(p)max(Build(p1,l,mid),Build(p1|1,mid1,r));
}
inline int PushUp(int p)
{return sum(p)max(sum(p1),sum(p1|1));
}
inline void PushDown(int p)
{if(laz(p)){sum(p1)laz(p);sum(p1|1)laz(p);laz(p1)laz(p);laz(p1|1)laz(p);laz(p)0;}
}
inline void Change(int p,int l,int r,int d)
{if(ll(p)r(p)r){sum(p)d,laz(p)d;return;}//printf(%lld ,p);PushDown(p);int midl(p)r(p)1;if(lmid)Change(p1,l,r,d);if(midr)Change(p1|1,l,r,d);PushUp(p);
}
inline int Query(int p,int l,int r)
{if(ll(p)r(p)r)return sum(p);PushDown(p);int midl(p)r(p)1,res0;if(lmid)resmax(Query(p1,l,r),res);if(midr)resmax(Query(p1|1,l,r),res);return res;
}
inline int low(int x)
{return x-x;
}
inline void add(int x,int d)
{while(xn)t[x]d,xlow(x);
}
inline int query(int x)
{int res0;while(x)rest[x],x-low(x);return res;
}
main()
{
// freopen(seq5.in,r,stdin);
// freopen(seq5.out,w,stdout);nread(),qread(),c1read(),c2read(),w1read(),w2read();for(int i1;in;i)a[i]read(),add(i,a[i]);Build(1,1,n);while(q--){int opt,x,y;optread(),xread(),yread();if(opt1)add(x,y),Change(1,x,x,y),a[x]y;else{int tmpQuery(1,x,y);if(tmpw1){puts(tetris);continue;}tmpquery(y)-query(x-1);if(tmpw1y-x1c1){puts(cont);continue;}else if(tmpw2y-x1c2){puts(tetris);continue;}else if(tmpw2){puts(cont);continue;}tmpquery(x-1c2)-query(x-1);int lx,rx-1c2,TL0,TR0;while(ry){if(tmpw2){TLl;break;}tmp-a[l];tmpa[r];}if(!TL){puts(cont);continue;}tmpquery(y)-query(y-c2);ly-c21,ry,TR0;while(lx){if(tmpw2){TRr;break;}tmp-a[r--];tmpa[--l];}if(!TR){puts(cont);continue;}tmpquery(TR)-query(TL-1);if(tmpw1TR-TL1c1)puts(cont);else puts(tetris);}}return 0;
}
