又是一天的爆零！！！！！
原本第一题 很容易做 竟然优化过度
丢了答案
1693: ksum
- Time Limit
- 1000 ms
- Memory Limit
- 524288 KBytes
- Judge
- Standard Judge
- Solved
- 18
- Submit
- 41
Description
Peter喜欢玩数组。NOIP这天，他从Jason手里得到了大小为n的一个正整数 数组。
Peter求出了这个数组的所有子段和，并将这n(n+1)/2个数降序排序，他想 知道前k个数是什么。
Input Format
输入文件名为 ksum.in。
输入数据的第一行包含两个整数 n 和 k。
接下来一行包含 n 个正整数，代表数组。
Output Format
输出文件名为 ksum.out。
输出 k 个数，代表降序之后的前 k 个数，用空格隔开。
Sample Input
input1
3 4
1 3 4 input2
3 3
10 2 7
Sample Output
output1
8 7 4 4 output2
19 12 10
Hint
测试点编号 n ≤ k ≤
1 100 5000
2 500 100000
3 1000 80000
4 1000 100000
5 10000 50000
6 20000 80000
7 50000 80000
8 100000 80000
9 100000 100000
10 100000 100000
对于所有数据，满足 ai≤10 9 k≤n(n+1)/2,n≤100000,k≤100000
明显的堆维护 对于一段连续序列 它的一系列次小值 一定是这段序列的子集；
只要每次取出 堆顶 将堆顶序列分别由 （l+1,r）&&(l,r-1)的子序列塞入堆中
进行堆维护即可 注意过程可能出现重复顶点 用哈希表维护即可；
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#define maxn 100010
using namespace std;
struct st
{
int l,r;
long long sum;
}mu[*maxn];
typedef pair<int,int> pa;
map <pa,bool>q1;
int n,m,k,l,n1,i;
int a[maxn];
void down(int x)
{
int fa=x,son;
while(fa*<=n1)
{
son=fa*;
if(mu[son+].sum>mu[son].sum&&son+<=n1)son++;
if(mu[fa].sum>mu[son].sum)break;
swap(mu[fa],mu[son]);
fa=son;
}
}
void up(int x)
{
int fa,son=x;
while(son/)
{
fa=son/;
if(mu[fa].sum>mu[son].sum)break;
swap(mu[fa],mu[son]);
son=fa;
}
}
void push (st x)
{
n1++; q1[pa(x.l,x.r)]=;
mu[n1]=x;
up(n1);
}
int main()
{
// freopen("ksum.in","r",stdin);
// freopen("ksum.out","w",stdout);
scanf("%d%d",&n,&k);
for(i=;i<=n;++i)
{
scanf("%d",&a[i]);
mu[].sum+=a[i];
}
n1=;mu[].l=;mu[].r=n;q1[pa(mu[].l,mu[].r)]=;
for(i=;i<=k;++i)
{
printf("%lld ",mu[].sum);
if(mu[].l<mu[].r)
{
st q;
q=mu[];
q.sum-=a[q.l];
q.l++;
if(!q1[pa(q.l,q.r)])
push(q);
q=mu[];
q.sum-=a[q.r];
q.r--;
if(!q1[pa(q.l,q.r)])
push(q);
}
mu[]=mu[n1--];
down();
}
}