bzoj 5209 [Tjoi2012]防御

bzoj 5209 [Tjoi2012]防御

​​ 题目描述

在一个塔防小游戏中，有很多防线。 每条防线由一排n个独立的防御体[1 : n]进行防御。

游戏过程中，会不断有敌人对防线进行攻击，每次攻击会指定防御体[l : r]进行攻击力为a的攻击。 第一防线具有护甲，护甲承受攻击后，对应的防御体所受到的伤害为攻击力，但护甲承受的伤害总量到达一定程度后就会破碎，此时防御体所受的伤害加倍。 目前第一防线的力量充足，玩家致力于对后面的防线的建设，不过为确认游戏进度和第一防线的情况，玩家会不时地将鼠标移动到第一防线的某个防御体上，以查看其所受到的伤害。

输入输出格式

输入格式：

第一行，两个整数n; q，分别表示防御体个数以及攻击和查询的总数。

第二行， n个数，表示每个防御体护甲的承受能力pi。

接下来 q 行，每行可能具有如下形式

A l r a 表示对防御体

l,l+1,\cdots,r

l,l+1,⋯,r 进行攻击力为a的攻击

Q x 表示查询防御体x目前所受到的伤害，初始时伤害为0

输出格式：

一行，一个整数，表示所有查询结果之和对1,000,000,009的余数

输入输出样例

输入样例#1： 复制

5 7 3 1 4 1 2 A 1 3 2 Q 2 A 1 4 1 Q 1 A 1 4 1 Q 2 Q 1 输出样例#1： 复制

16 说明

样例解释

3/0 1/0 4/0 1/0 2/0

[A 1 3 2]

1/2 2 2/2 1/0 2/0

[Q 2] ! 2

[A 1 4 1]

3 4 1/3 1 2/0

[Q 1] -> 3

[A 1 4 1]

5 6 4 3 2/0

[Q 2] -> 6

[Q 1] -> 5

数据范围

30%的数据， q ≤ 1000

100%的数据， 1 ≤ n ≤ 100000， 1 ≤ q ≤ 100000， 0 ≤ pi ≤ 1000000， 0 ≤ a ≤ 10000

题意很坑 需要枚举题意：如果护甲被打爆 那个这次被打爆不会计算两倍答案

设a数组记录打爆前的答案 flag表示是否打爆 每个节点维护min id 分别表示最小值和 最小值来自哪里

然后每次修改以后检查全局是否存在<=0的节点 如果存在就暴力while循环更改id这个点的情况 直到没有

#include#include#include#define lc (x<<1)#define rc (x<<1|1)using namespace std;const int mod=1e9+9;const int N=1e5+10;const int inf=0x3f3f3f3f;struct node{ int mn,tag,id,v;}tree[N<<2];inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}inline void update(int x){ tree[x].mn=inf; if(tree[lc].mn>1; build(lc,l,mid);build(rc,mid+1,r);update(x);}int n,q,a[N],ans;bool flag[N];inline void doa(int x,int v){ tree[x].v+=v;tree[x].tag+=v;tree[x].mn-=v;}inline void pushdown(int x){ if (!tree[x].tag) return;static int tag; tag=tree[x].tag;tree[x].tag=0;doa(lc,tag);doa(rc,tag);}inline void modify(int x,int l,int r,int l1,int r1,int v){ if (l1<=l&&r1>=r){doa(x,v);return;}int mid=l+r>>1;pushdown(x); if (l1<=mid) modify(lc,l,mid,l1,r1,v); if (r1>mid) modify(rc,mid+1,r,l1,r1,v);update(x);}inline void query(int x,int l,int r,int p){ if (l==r){flag[l]=1;a[l]=tree[x].v;tree[x].v=tree[x].tag=0;tree[x].mn=inf;return;} int mid=l+r>>1;pushdown(x); if (p<=mid) query(lc,l,mid,p);else query(rc,mid+1,r,p);update(x);}inline int qr(int x,int l,int r,int p){ if(l==r){return tree[x].v+a[l]+tree[x].v*flag[l];}int mid=l+r>>1;pushdown(x); if (p<=mid) return qr(lc,l,mid,p);else return qr(rc,mid+1,r,p);}inline void inc(int &x,int v){x=x+v>=mod?x+v-mod:x+v;}int main(){ freopen("bzoj5209.in","r",stdin); n=read();q=read();build(1,1,n); while(q--){ char ch=gc();while(ch!='A'&&ch!='Q') ch=gc(); if(ch=='A'){static int l,r,x; l=read();r=read();x=read(); modify(1,1,n,l,r,x); while(tree[1].mn<=0) query(1,1,n,tree[1].id); } if(ch=='Q') inc(ans,qr(1,1,n,read())); }printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。