HDU6058-Kanade's sum 链表+思维

xiaoxiao2021-02-28  96

传送门

题意:

给出n、k、1~n个不同的数

求数列所有区间第k小的数的和的值

思路:

1、注意到 1~n个不同的数,且k<=min(n,80) 的数字特征

2、按数字从大到小的顺序往set容器加入数字的位置,对于每个数,枚举左边移动n(n 为 1~k 或 一直移动到左边界)个数,右边相应移动(k-n  或 一直移动到右边界)个数

#include<bits/stdc++.h> using namespace std; #define N 500005 #define LL long long int l[N]; //l[i] 表示 i左边 第一个 比 i 大的数 int r[N]; int index[N]; //index[i] 表示 i 的位置 int main() { set<int>se; set<int>::iterator it; int t; scanf("%d",&t); while(t--){ LL ans = 0; se.clear(); int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ int a; scanf("%d",&a); index[a] = i; } l[0] = 0; //设位置 0 为 左边最大 r[0] = n+1; //设位置 n+1 为 右边最大 se.insert(0); for(int i=n;i>=1;i--){ se.insert(index[i]); it = se.find(index[i]); it--; // 插入 index[i] 并且 更新左右数的相对关系 l[index[i]] = *it; r[index[i]] = r[*it]; r[*it] = index[i]; l[r[index[i]]] = index[i]; int l1,r1; l1 = index[i]; for(int j=0;j<k&&l1;j++){ //向左移动k个单位,或 l1 为 0 l1 = l[l1]; } r1 = l1; for(int j=0;j<k&&r1!=n+1;j++){ //再让r1 从 l1 向左移动k个单位,或 r1 为 n+1 r1 = r[r1]; } for(int j=0;j<k;j++){ if(l1==index[i] || r1==n+1) break; ans += (LL)i * (r[l1]-l1) * (r[r1]-r1) ; l1 = r[l1]; r1 = r[r1]; } } printf("%lld\n",ans); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-36434.html

最新回复(0)