2017 Multi-University Training Contest - Team 3 Kanade's sum hd6058
2024-09-04 12:26:56
地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=6058
题目:
Kanade's sum
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 505 Accepted Submission(s): 176
Problem Description
Give you an array A[1..n]of length n.
Let f(l,r,k) be the k-th largest element of A[l..r].
Specially , f(l,r,k)=0 if r−l+1<k.
Give you k , you need to calculate ∑nl=1∑nr=lf(l,r,k)
There are T test cases.
1≤T≤10
k≤min(n,80)
A[1..n] is a permutation of [1..n]
∑n≤5∗105
Input
There is only one integer T on first line.
For each test case,there are only two integers n,k on first line,and the second line consists of n integers which means the array A[1..n]
Output
For each test case,output an integer, which means the answer.
Sample Input
1
5 2
1 2 3 4 5
Sample Output
30
Source
思路:
很容易想到按公式算是不可行的(O(n^2)的时间复杂度),然后想到枚举计算每个数的贡献:即第k大为x的区间个数乘以x
然后只要考虑怎么快速求出第k大为x的区间个数。如果能知道左边大于x的80个数的位置和右边大于x的80个数的位置就可以计算区间个数了。
之后想到用从小到大枚举或者从大到小,用链表维护即可。
比赛时用的set模拟的,结果被卡了,T的连妈都不认识。还是觉得时限卡太紧了。
#include <bits/stdc++.h> using namespace std; #define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-;
const double pi=acos(-1.0);
const int K=1e6+;
const int mod=1e9+; int n,k,p[K],pre[K],nxt[K],pos[K],tl[],tr[];
LL ans; int main(void)
{
int t;cin>>t;
while(t--)
{
ans=;
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d",p+i),pos[p[i]]=i;
for(int i=;i<=n;i++)
pre[i]=i-,nxt[i]=i+;
pre[]=,nxt[n]=n+;
for(int i=;i<=n;i++)
{
int la=,lb=;
for(int j=pos[i];j>&&la<=k;j=pre[j])
tl[la++]=j-pre[j];
for(int j=pos[i];j<=n&&lb<=k;j=nxt[j])
tr[lb++]=nxt[j]-j;
for(int j=;j<la;j++)
if(k-j-<lb)
ans+=i*1LL*tl[j]*tr[k-j-];
pre[nxt[pos[i]]]=pre[pos[i]];
nxt[pre[pos[i]]]=nxt[pos[i]];
}
printf("%lld\n",ans);
}
return ;
}
最新文章
- 阿里巴巴集团2016校园招聘-Python工程师笔试题(附加题+部分答案)
- 【leetcode❤python】 400. Nth Digit
- iOS开发----调用地图导航
- 自己封装的OKhttp请求
- java 地址记录
- UVALive 2238 Fixed Partition Memory Management(二分完美匹配)
- URAL 1776 C - Anniversary Firework DP
- C# 操作mongodb 分组
- mudOS配置
- AIX 中以并发模式挂载vg
- js并行加载,顺序执行
- Java与算法之(6) - 八皇后问题
- vue -- v-cloak解决刷新或者加载出现闪烁(显示变量)
- 二叉查找树的C++实现
- Dynamics 365 Customer Engagement V9 活动源功能报错的解决方法
- Java将Excel解析为数组集合
- 最近的AI
- IncDec Sequence(差分)
- POJ1942-Paths On a Grid-组合数学
- CentOS7服务器上部署深度/机器学习环境推荐首选anaconda3
热门文章
- hdu 4739(状态压缩)
- react-native新导航组件react-navigation详解
- CPU GPU设计工作原理《转》
- WebStorm Cordova 环境搭建
- 【BZOJ5072】[Lydsy十月月赛]小A的树 树形DP
- 《从零开始学Swift》学习笔记(Day67)——Cocoa Touch设计模式及应用之MVC模式
- Zabbix添加web页面监控告警
- Code Forces 26C Dijkstra?
- 粘性会话 session affinity sticky session requests from the same client to be passed to the same server in a group of servers
- PHP_OS常量使用方法