长春网站开发推荐,网站访问速度优化工具,贵港公司做网站,信阳网站建设汉狮报价4631: 踩气球 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 224 Solved: 114[Submit][Status][Discuss]Description 六一儿童节到了#xff0c; SHUXK 被迫陪着M个熊孩子玩一个无聊的游戏#xff1a;有N个盒子从左到右排成一排#xff0c;第i个盒子里装着Ai个气球。SH… 4631: 踩气球 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 224 Solved: 114[Submit][Status][Discuss] Description 六一儿童节到了 SHUXK 被迫陪着M个熊孩子玩一个无聊的游戏有N个盒子从左到右排成一排第i个盒子里装着Ai个气球。 SHUXK 要进行Q次操作每次从某一个盒子里拿出一个没被踩爆的气球然后熊孩子们就会立刻把它踩爆。 这M个熊孩子每个人都指定了一个盒子区间[Li, Ri]。 如果某一个时刻一个熊孩子发现自己选定的盒子区间[Li, Ri]中的所有气球都已经被踩爆了他就会非常高兴显然之后他一直会很高兴。 为了不辜负将自己的任务强行塞给 SHUXK 的那个人的期望 SHUXK 想向你询问 他每次操作过后会有多少个熊孩子很高兴。 Input 第一行包含两个正整数N和M分别表示盒子和熊孩子的个数。 第二行包含N个正整数Ai 1 Ai 10^5表示每个盒子里气球的数量。 以下M行每行包含两个正整数Li, Ri 1 Li Ri N分别表示每一个熊孩子指定的区间。 以下一行包含一个正整数Q表示 SHUXK 操作的次数。 以下Q行每行包含一个正整数X表示这次操作是从第X个盒子里拿气球。为了体现在线我们对输入的X进行了加密。 假设输入的正整数是x那么真正的X (x Lastans − 1)Mod N 1。其中Lastans为上一次询问的答案。对于第一个询问 Lastans 0。 输入数据保证1 x 10^9 且第X个盒子中有尚未被踩爆的气球。 N 10^5 ,M 10^5 ,Q 10^5 Output 包含Q行每行输出一个整数表示 SHUXK 一次操作后询问的 答案。答案的顺序应与输入数据的顺序保持一致。 Sample Input 5 3 1 1 1 1 1 5 5 2 2 1 3 5 4 2 5 2 3 Sample Output 0 1 1 2 3 【样例说明】 实际上每次操作的盒子是 4 2 1 3 5 在第二次操作后第二个熊孩子会高兴 区间[2,2]中的气球已经全部被踩爆。 在第四次操作后第三个熊孩子会高兴区间[1,3]中的气球已经全部被踩爆。 在第五次操作后第一个熊孩子会高兴区间[5,5]中的气球已经全部被踩爆。 HINT Source Solution 比较好想的一道题 首先对序列建线段树把M个区间建到线段树上在线段树的相应节点上记录 维护区间的A[]值和 修改操作相当于单点-1 当一个区间的和0时更新这个区间上的熊孩子区间的答案然后统计ans 期望的时间复杂度大概是$O(MlogN)$ Code #includeiostream
#includecstdio
#includecstring
#includealgorithm
#includecmath
#includevector
using namespace std;
inline int read()
{int x0,f1; char chgetchar();while (ch0 || ch9) {if (ch-) f-1; chgetchar();}while (ch0 ch9) {xx*10ch-0; chgetchar();}return x*f;
}
#define MAXN 100010
int N,M,Q,size[MAXN],ans,last,A[MAXN];
struct SegmentTreeNode{int l,r,sum; vectorintv; }tree[MAXN2];
inline void Update(int now) {tree[now].sumtree[now1].sumtree[now1|1].sum;}
inline void PushUp(int now)
{if (tree[now].sum) return;int lentree[now].v.size(),ltree[now].l,rtree[now].r;for (int i0; ilen-1; i)size[ tree[now].v[i] ]-r-l1;for (int i0; ilen-1; i)if (!size[ tree[now].v[i] ]) ans;tree[now].v.clear();
}
void BuildTree(int now,int l,int r)
{tree[now].ll; tree[now].rr;if (lr) {tree[now].sumA[l]; return;}int mid(lr)1;BuildTree(now1,l,mid);BuildTree(now1|1,mid1,r);Update(now); PushUp(now);
}
inline void Change(int now,int pos,int D)
{int ltree[now].l,rtree[now].r;if (lr) {tree[now].sumD; PushUp(now); return;}int mid(lr)1;if (posmid) Change(now1,pos,D);if (posmid) Change(now1|1,pos,D);Update(now); PushUp(now);
}
inline void Cover(int now,int L,int R,int id)
{int ltree[now].l,rtree[now].r;if (Ll Rr) {tree[now].v.push_back(id); size[id]R-L1; return;}int mid(lr)1;if (Lmid) Cover(now1,L,R,id);if (Rmid) Cover(now1|1,L,R,id);Update(now); PushUp(now);
}
inline int GetX(int x) {return (xlast-1)%N1;}
int main()
{Nread(),Mread();for (int i1; iN; i) A[i]read();BuildTree(1,1,N);for (int L,R,i1; iM; i) Lread(),Rread(),Cover(1,L,R,i);Qread();for (int x,i1; iQ; i) xGetX(read()),Change(1,x,-1),printf(%d\n,lastans);return 0;
} 总感觉有种不科学的....毕竟就用了10分钟就A了...转载于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5793494.html
