K Seq HihoCoder - 1046 || BZOJ4504 k个串
这题与超级钢琴类似,然而重复的不重复计算贡献。。
那么先求出数组nxt,nxt[i]表示第i个元素之后的第一个与其相等的元素的下标,不存在则nxt[i]=0
考虑取的区间左端点为1时的情况。
将读入序列a中相等元素都只保留最先出现的,其余变为0,然后求前缀和,得到数组b。
此时可以知道,设f(l,r)为取下标在[l,r]区间内数时的答案,那么f(1,r)=b[r]。
考虑取的区间左端点为2时的情况。如何维护b数组,使得新的b数组也满足f(2,r)=b[r]?
手模样例区间左端点为1和2时符合要求的b。
样例:
7 5
3 -2 1 2 2 1 3
l=1: 3 1 2 4 4 4 4
l=2: 0 -2 -1 1 1 1 4
可以发现,做的操作相当于将b数组内下标在[1,nxt[1]-1]区间内的数减了(原来的)b[1]。
进一步推出,左端点为l时的b数组变到左端点l+1的b数组,就相当于将下标在[l,nxt[l]-1]区间内的数减了(原来的)b[l]。
(当然如果nxt[i]=0,那么就是将[l,n]内减b[l])
因此,可以用可持久化线段树处理出左端点为每一个位置时的b数组。可持久化线段树如果要传标记的话常数会很大(复杂度应该是对的...大概吧?),所以可以标记永久化
(不知道为什么网上的标记永久化那么长?吓得我还以为自己写错了233333)
(我写标记永久化时候困难重重,最后发现标记含义的定义还是类比普通线段树最容易实现(就是除当前节点外,以当前节点为根的子树内所有点的对应值都应加上当前节点的加法tag),另外给标记和记录的值一个明确的定义对于写清楚代码非常重要)
这样子之后就可以用类似超级钢琴的做法去做了...才怪。难道你真的跟我一样想要去写可持久化的带区间修改的区间第k大这样子一看就不靠谱的东西?
可以发现每一次对给定某一个b数组的查询,每次的区间都是一样的,一定是第一次第1大,第二次第2大,...
当然就可以用超级钢琴的后一种做法去做了(优先队列维护一下哪个b数组,哪一段区间的最大值是多少,在哪里,当某一段区间最大值被取出后,把该区间除了最大值所在位置剩下的最多两段取最大值放回优先队列)。'
(似乎也可以考虑暴力将原来的最大值加一个-inf?这样子下一次查找找到的就是该区间的次大啦(我没试过))
错误记录:
1.不知道为什么想到去维护最小值了,怎么过的样例啊
2.82-83行i+1写成i
#include<cstdio>
#include<algorithm>
#include<queue>
#include<tr1/unordered_map>
#define inf 0x3f3f3f3f3f3f3f3f
#define mid ((l+r)>>1)
using namespace std;
using namespace tr1;
typedef long long LL;
typedef pair<LL,LL> P;
LL lc[],rc[],addv[],mem;
//addv[i]表示i区间加法tag
P maxn[];//一对值:区间(只考虑自身及其下节点的标记)的最大值及下标
LL L,R,x;
LL root[],nxt[],a[],b[];
tr1::unordered_map<LL,LL> ttt1;
void build(LL l,LL r,LL &num)
{
num=++mem;
if(l==r) {maxn[num]=P(b[l],l);return;}
build(l,mid,lc[num]);build(mid+,r,rc[num]);
maxn[num]=max(maxn[lc[num]],maxn[rc[num]]);
}
void addx(LL l,LL r,LL &num)
{
LL t=num;num=++mem;lc[num]=lc[t];rc[num]=rc[t];maxn[num]=maxn[t];addv[num]=addv[t];
if(L<=l&&r<=R)
{
addv[num]+=x;maxn[num].first+=x;
return;
}
if(L<=mid) addx(l,mid,lc[num]);
if(mid<R) addx(mid+,r,rc[num]);
maxn[num]=max(maxn[lc[num]],maxn[rc[num]]);
maxn[num].first+=addv[num];
}
P query(LL l,LL r,LL num)
{
if(L<=l&&r<=R) return maxn[num];
P ans=P(-inf,);
if(L<=mid) ans=max(ans,query(l,mid,lc[num]));
if(mid<R) ans=max(ans,query(mid+,r,rc[num]));
ans.first+=addv[num];
return ans;
}
struct Info
{
Info(LL a=,LL b=,LL c=,LL d=,LL e=)
:ans(a),l(b),r(c),st(d),pos(e)
{}
LL ans,l,r,st,pos;
//root[st]中,[l,r]内最大值是ans,在pos位置
friend bool operator<(const Info &a,const Info &b)
{
return a.ans<b.ans;
}
};
LL n,k;
priority_queue<Info> q;
int main()
{
LL i;P t;Info t2;
scanf("%lld%lld",&n,&k);
for(i=;i<=n;i++) scanf("%lld",&a[i]);
for(i=;i<=n;i++)
{
b[i]=b[i-];
if(ttt1.count(a[i])==)
b[i]+=a[i];
else
nxt[ttt1[a[i]]]=i;
ttt1[a[i]]=i;
}
build(,n,root[]);
L=,R=n,t=query(,n,root[]);
q.push(Info(t.first,,n,,t.second));
for(i=;i<n;i++)
{
root[i]=root[i-];
L=i,R=i,x=-query(,n,root[i]).first;
L=i,R=nxt[i]?nxt[i]-:n,addx(,n,root[i]);
L=i+/**/,R=n,t=query(,n,root[i]);
q.push(Info(t.first,i+,n,i,t.second));//
}
for(i=;i<k;i++)
{
t2=q.top();q.pop();
L=t2.l,R=t2.pos-;
if(L<=R)
{
t=query(,n,root[t2.st]);
q.push(Info(t.first,L,R,t2.st,t.second));
}
L=t2.pos+,R=t2.r;
if(L<=R)
{
t=query(,n,root[t2.st]);
q.push(Info(t.first,L,R,t2.st,t.second));
}
}
t2=q.top();
printf("%lld",t2.ans);
return ;
}
最新文章
- 极其简单的搭建eclipse的android开发环境
- Erlang 从入门到精通(一) 下载安装
- mssqlserver 批量插入示例
- python学习笔记24(路径与文件 (os.path包, glob包))
- 使用bacula实现Linux的远程备份和还原
- Asp.Net MVC5 格式化输出时间日期
- EF中加载实体的方式
- QF——UI之几种常用的隐藏键盘的方法
- 关于cvScalar的那些事
- ES6的Symbol
- DB2数据库代码页和实例代码页的区别(解决DB2乱码问题)
- CemtOS7更改yum网易 阿里云的yum源。
- ubuntu16.04下载安装navicate
- LINUX系统下MySQL 压力测试工具super smack
- js上传文件带参数,并且,返回给前台文件路径,解析上传的xml文件,存储到数据库中
- iOS:ASIHttpRequest虽不更新,但仍值得详细了解
- 封装axios方法之一
- 彻底解决_OBJC_CLASS_$_某文件名";, referenced from:问题
- TRANSLATE(转换大/小写并替换字符)
- js获取指定小时日期格式化
热门文章
- 【ZJOI2017 Round1练习】D4T2 trie(贪心,状压DP)
- Spring基础入门(一)
- HAProxy教程收集
- LINUX 内核结构
- Linux学习系列之Inotify+Rsync实现实时数据同步
- 将github上的项目源码导入eclipse详细教程
- 在GNS3下使用Cisco SDM 的教程
- [VueJS + Typescript] Decouple Dependencies Using IoC Containers in Vue with TypeScript and InversifyJS
- ubuntu11.04 编译ffmpeg2.7 并生成 ffplay进行流媒体測试
- 华为OJ2288-合唱队(最长递增子序列)