关键词:
2527: [Poi2011]Meteors
Time Limit: 60 Sec Memory Limit: 128 MB Submit: 1807 Solved: 646 [Submit][Status][Discuss]Description
这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。
BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石。
输入:
第一行是两个数N,M。
第二行有M个数,第i个数Oi表示第i段轨道上有第Oi个国家的太空站。
第三行有N个数,第i个数Pi表示第i个国家希望收集的陨石数量。
第四行有一个数K,表示BIU预测了接下来的K场陨石雨。
接下来K行,每行有三个数Li,Ri,Ai,表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中(如果Li<=Ri,就是Li,Li+1,...,Ri,否则就是Ri,Ri+1,...,m-1,m,1,...,Li),向区间中的每个太空站提供Ai单位的陨石样本。
输出:
N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。如果到第K波结束后仍然收集不到,输出NIE。
数据范围:
Input
Output
Sample Input
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
Sample Output
NIE
1
#include <vector> #include <cstdio> using namespace std; typedef long long ll; const int maxn = 300000 + 10, maxm = 300000 + 10, maxk = 300000 + 10, INF = 0x7f7f7f7f; int n, m, k; ll bit[maxm] = {0}; inline void Update(int x, int val){ for(int i = x; i <= m; i += i & -i) bit[i] += val; } inline ll Query(int x){ ll s = 0; for(int i = x; i; i -= i & -i) s += bit[i]; return s; } vector<int> w[maxn]; int p[maxn], id[maxn], ans[maxn]; struct Node{ int l, r, val; Node(){} Node(int _l, int _r, int _v): l(_l), r(_r), val(_v){} void read(){ scanf("%d %d %d", &l, &r, &val); } }q[maxk]; inline void Just_Do_It(int x, int f){ if(q[x].l <= q[x].r){ Update(q[x].l, f * q[x].val); Update(q[x].r + 1, -f * q[x].val); } else{ Update(q[x].l, f * q[x].val); Update(1, f * q[x].val); Update(q[x].r + 1, -f * q[x].val); } } int T = 0, tp[maxn]; bool mark[maxn] = {false}; void solve(int ql, int qr, int vl, int vr){ if(ql > qr) return; if(vl == vr){ for(int i = ql; i <= qr; i++) ans[id[i]] = vl; return; } int mid = vl + vr >> 1; while(T < mid) Just_Do_It(++T, 1); while(T > mid) Just_Do_It(T--, -1); int cnt = 0; ll sum; for(int size, i = ql; i <= qr; i++){ sum = 0; size = w[id[i]].size(); for(int j = 0; j < size; j++){ sum += Query(w[id[i]][j]); if(sum >= p[id[i]]) break; } if(sum >= p[id[i]]){ mark[i] = true; cnt++; } else mark[i] = false; } int ll = ql, rr = ll + cnt; for(int i = ql; i <= qr; i++) if(mark[i]) tp[ll++] = id[i]; else tp[rr++] = id[i]; for(int i = ql; i <= qr; i++) id[i] = tp[i]; solve(ql, ll - 1, vl, mid); solve(ll, qr, mid + 1, vr); } int main(){ scanf("%d %d", &n, &m); for(int x, i = 1; i <= m; i++){ scanf("%d", &x); w[x].push_back(i); } for(int i = 1; i <= n; i++) scanf("%d", p + i); scanf("%d", &k); for(int i = 1; i <= k; i++) q[i].read(); k++; q[k] = Node(1, m, INF); for(int i = 1; i <= n; i++) id[i] = i; solve(1, n, 1, k); for(int i = 1; i <= n; i++) if(ans[i] == k) puts("NIE"); else printf("%d ", ans[i]); return 0; }
bzoj2527:[poi2011]meteors
这个。。。一開始用的是longlong然后改成int就wa了。。。。时间垫底。。。。。可怕全局分治 然后用线段树维护的时候直接永久化标记 不用下传然后这一题和上一道树套树一样。又是由于自己傻逼少了一倍的线段树节... 查看详情
bzoj2527[poi2011]meteors:整体二分
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2527题意: 有n个国家和m个空间站,每个空间站都属于一个国家,一个国家可以有多个空间站,所有空间站按照顺序形成一个环,也就是说,m号空间站和1号空间站相邻。 现... 查看详情
bzoj2527[poi2011]meteors整体二分+树状数组
题目描述有N个成员国。现在它发现了一颗新的星球,这颗星球的轨道被分为M份(第M份和第1份相邻),第i份上有第Ai个国家的太空站。这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。BIU的第i个成员国希望能够... 查看详情
bzoj2527meteors-整体二分-树状数组
DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinanearbygalaxy.Theplanetisunsuitableforcolonisationduetostrangemeteorshowers,whichontheotherhandmakeitanexceptionallyinteresti 查看详情
[poi2011]meteors题解
题目大意: 给定一个环,每个节点有一个所属国家,k次事件,每次对[l,r]区间上的每个点点权加上一个值,求每个国家最早多少次操作之后所有点的点权和能达到一个值。思路: 整体二分(二分答案),对于每个国家,... 查看详情
[poi2011]met-meteors
题面题解首先我们尝试暴力,那么就对每个点二分一下即可。我们发现单独二分复杂度太高,而且有些地方很浪费,如求前缀和等。那么我们就想,能否将它们合并在一起二分呢?于是就有了整体二分整体二分即可。代码#include&... 查看详情
[poi2011]met-meteors(整体二分+树状数组)
题意给定一个环,每个节点有一个所属国家,k次事件,每次对[l,r]区间上的每个点点权加上一个值,求每个国家最早多少次操作之后所有点的点权和能达到一个值题解一个一个国家算会T。这题要用整体二分。我们二分mid给所有... 查看详情
p3527[poi2011]met-meteors(整体二分)(代码片段)
P3527[POI2011]MET-Meteors(整体二分)考虑整体二分答案kkk。每次对于[l,m][l,m][l,m]区间使用BITBITBIT维护差分进行区间修改。然后对于[ql,qr][ql,qr][ql,qr]就单点查询然后求和,特判是否满足,若大于等于丢左子区间,否则丢右... 查看详情
bzoj2213[poi2011]differencedp
【BZOJ2213】[Poi2011]DifferenceDescriptionAwordconsistingoflower-caselettersoftheEnglishalphabet(‘a‘-‘z‘)isgiven.Wewouldliketochooseanon-emptycontiguous(i.e.one-piece)fragmentofthewordsoastomaximisethed 查看详情
bzoj2529:[poi2011]sticks
2529:[Poi2011]SticksTimeLimit:10Sec MemoryLimit:128MBSec SpecialJudgeSubmit:257 Solved:133[Submit][Status][Discuss]DescriptionLittleJohnnywasgivenabirthdaypresentbyhis 查看详情
bzoj2530[poi2011]party
2530:[Poi2011]PartyTimeLimit:10Sec MemoryLimit:128MBSec SpecialJudgeSubmit:342 Solved:196[Submit][Status][Discuss]DescriptionByteasarintendstothrowupaparty.Naturally,h 查看详情
[bzoj]2276:[poi2011]temperature
2276:[Poi2011]TemperatureTimeLimit: 20Sec MemoryLimit: 32MBSubmit: 731 Solved: 334[Submit][Status][Discuss]DescriptionTheByteotianInstituteofMeteorology(BIM)m 查看详情
bzoj2213:[poi2011]difference
DescriptionAwordconsistingoflower-caselettersoftheEnglishalphabet(‘a‘-‘z‘)isgiven.Wewouldliketochooseanon-emptycontiguous(i.e.one-piece)fragmentofthewordsoastomaximisethedifferenceinthenumberofoccurre 查看详情
bzoj-2276:[poi2011]temperature(单调队列)
2276:[Poi2011]TemperatureTimeLimit: 20Sec MemoryLimit: 32MBSubmit: 763 Solved: 352[Submit][Status][Discuss]DescriptionTheByteotianInstituteofMet 查看详情
bzoj_2212_[poi2011]treerotations_线段树合并
BZOJ_2212_[Poi2011]TreeRotations_线段树合并DescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatikus.Ithassomeinterestingfeatures:Thetreeconsistsofstraightbranches,bifurcationsandleaves.The 查看详情
bzoj2212[poi2011]treerotations线段树合并
DescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatikus.Ithassomeinterestingfeatures:Thetreeconsistsofstraightbranches,bifurcationsandleaves.Thetrunkstemmingfromthegroundisalsoabranc 查看详情
[bzoj2212][poi2011]treerotations(线段树合并)(代码片段)
2212:[Poi2011]TreeRotationsTimeLimit:20Sec MemoryLimit:259MBSubmit:1562 Solved:614[Submit][Status][Discuss]DescriptionByteasarthegardenerisgrowingararetreecalledRotatusInformatik 查看详情
bzoj2212[poi2011]treerotations
题解:交换某节点的两棵子树仅对 此节点子树对答案的贡献 有影响Dfs,启发式合并时顺便求逆序对即可,贪心交不交换O(nlogn*logn)Noname讲过一种合并Treap求逆序对,仅需O(nlogn),还不会 查看详情