题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2006
数据传送门:noi_2010_piano
这题很经典!很好!
首先肯定是求前缀和,然后搞n个结构体,第i个表示左端点在i的线段的最值
每次取出最大的结构体进行拓展,需要用函数式线段树来支持区间k大
时间复杂度:O(k*log(值域))
另外这题还有ST表的做法,但还不是很会 qwq
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 500000+9; const int M = 20000000+9; const int BAS = 500000010; const int INF = 1000010000; int n,k,L,R,arr[N]; struct Query{ int pos,num,val; bool operator < (const Query & B) const { return val < B.val; } }; priority_queue<Query> que; namespace Chair_Tree{ #define CT Chair_Tree int ch[M][2],sum[M],cnt,root[N],ans_tmp; void insert(int p, int &w, int l, int r, int v) { w = ++cnt; sum[w] = sum[p] + 1; memcpy(ch[w],ch[p],sizeof(ch[0])); if (l < r) { int mid = l + r + 1 >> 1; if (v < mid) insert(ch[p][0], ch[w][0], l, mid-1, v); else insert(ch[p][1], ch[w][1], mid, r, v); } } inline void insert(int p, int w) { insert(root[p-1], root[p], 1, INF, w); } void query(int p, int w, int l, int r, int num) { if (l == r) ans_tmp = l; else { int mid = l + r + 1 >> 1; if (sum[ch[w][1]] - sum[ch[p][1]] >= num) query(ch[p][1], ch[w][1], mid, r, num); else query(ch[p][0], ch[w][0], l, mid-1, num - (sum[ch[w][1]] - sum[ch[p][1]])); } } inline int query(int l, int r, int num) { query(root[l-1],root[r],1,INF,num); return ans_tmp; } }; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main(){ n = read(); k = read(); L = read(); R = read(); for (int i=1;i<=n;i++) arr[i] = arr[i-1] + read(); for (int i=1;i<=n;i++) CT::insert(i,arr[i] + BAS); for (int i=1;i+L-1<=n;i++) { Query tmp; tmp.pos = i; tmp.num = 1; tmp.val = CT::query(i+L-1, min(n,i+R-1), 1) - BAS - arr[i - 1]; que.push(tmp); } LL vout = 0; for (int i=1,p;i<=k;i++) { Query tmp = que.top(); que.pop(); vout += tmp.val; if (tmp.num < R - L + 1) { tmp.num++; p = tmp.pos; if (n - (p+L-1) + 1 < tmp.num) continue; tmp.val = CT::query(p+L-1, min(n,p+R-1), tmp.num) - arr[p - 1] - BAS; que.push(tmp); } } printf("%lld\n",vout); return 0; }
I think this is among the most significant information for me. And i’m glad reading your article. But want to remark on some general things, The web site style is ideal, the articles is really nice : D. Good job, cheers
Wow, attractive site. Thnx …|
417649 887467Chaga mushroom tea leaf is thought-about any adverse health elixir at Spain, Siberia and lots of n . Countries in europe sadly contains before you go ahead significantly avoidable the main limelight under western culture. Mushroom 496716
775009 48834very good post, i definitely enjoy this incredible internet site, persist with it 408956
955064 760605Wonderful post man, keep the nice work, just shared this with my friendz 134700
724091 797185Really good post. I just stumbled upon your weblog and wanted to say that Ive truly enjoyed surfing about your weblog posts. Right after all I will be subscribing to your feed and I hope you write once more extremely soon! 789978
408297 432383Someone necessarily assist to make critically articles Id state. This is the first time I frequented your web page and thus far? I amazed with the analysis you produced to make this actual submit incredible. Outstanding activity! 648867
139956 176985Located your weblog and decided to have a study on it, not what I usually do, but this blog is fantastic. Awesome to see a site thats not spammed, and in fact makes some sense. Anyway, fantastic write up. 492635
606399 277872need to do initial? Most entrepreneurs are so overwhelmed with their online business plans that 114679
982826 39848I usually cant discover it in me to care enough to leaves a comment for articles on the internet but this was really pretty great, thanks and maintain it up, Ill check back once more 751176
878171 795886Absolutely composed content material , Genuinely enjoyed examining . 236511
438516 638207Cause thats required valuable affiliate business rules to get you started on participating in circumstances appropriate for your incredible web-based business concern. Inernet marketing 648361
329037 825327 Nice post. I learn something more challenging on different blogs everyday. It will always be stimulating to read content from other writers and practice slightly something from their store. Id prefer to use some with the content on my weblog whether you dont mind. Natually Ill give you a link on your web blog. Thanks for sharing. 853847
399485 384160Yay google is my king aided me to find this excellent web site ! . 540773
218581 80250You produced some decent points there. I looked online to the problem and discovered many people is going in addition to making use of your site. 264119
I was studying some of your blog posts on this website and I think this website is real informative! Continue putting up.