HDU 6058列挙Kanade's sum
5300 ワード
タイトル
Kanade's sum
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2496 Accepted Submission(s): 1037
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+1Give 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
チェーンテーブルのコードは、チェーンテーブルで彼より大きい数を探すたびに時間を節約し、Nが大きくなるにつれて時間を節約します.
Kanade's sum
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2496 Accepted Submission(s): 1037
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 , 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
题目大意
给我们一个数组A，给了我们一个区间，变成for循环就是for(l从1到n) for(r从l到n) 求区间内第K大的数，把这些第K大的数累计求和
解题思路
采用枚举的思想，从每一个数组中的元素遍历他的左右边看分别有多少个比他大的数，这样我们就可以知道该元素可以有多少个第K大的组合可能
#include
#include
using namespace std;
#define read(a) scanf("%d",&a)
#define LL long long
const int maxn=500000+10;
int a[maxn];
int l[maxn],r[maxn];
int main()
{
//freopen("1003.in", "r", stdin);
//freopen("data.out", "w", stdout);
int t;
read(t);
while(t--)
{
int n,k;
read(n);
read(k);
for(int i=0;ik)
break;
if(a[j]>a[i])
{
r[rcnt++]=j-i;//r[rcnt] rcnt a[i] a[i] ， ， j,
// a[i] ， rnum=1， ,
// ，
}
}
if(j>=n)
r[rcnt]=n-i; // a[i] k ，
// a[i] rcnt-1 ，
// a[i] righht，
//（ right ， ）
// r[rcnt] right a[i]
for(j=i-1;j>=0;j--)
{
if(lcnt>k)
break;
if(a[j]>a[i])
{
l[lcnt++]=i-j;//
}
}
if(j<=0)
l[lcnt]=i+1;//
for(j=0;j=rcnt)
continue;
int lnum=l[j+1]-l[j];
int rnum=r[k-j]-r[k-j-1];
ans+=(LL)a[i]*lnum*rnum;
}
}
printf("%lld
",ans);
}
return 0;
}
チェーンテーブルのコードは、チェーンテーブルで彼より大きい数を探すたびに時間を節約し、Nが大きくなるにつれて時間を節約します.
#include
#include
#include
using namespace std;
#define LL long long
#define read(a) scanf("%d",&a)
const int maxn=5*1e5+10;
int pre[maxn],nex[maxn],pos[maxn],f[maxn],b[maxn],a[maxn],n,k;
void dele(int p)//
{
if(p==1)
pre[nex[p]]=pre[p];
else if(p==n)
nex[pre[p]]=nex[p];
else
{
pre[nex[p]]=pre[p];
nex[pre[p]]=nex[p];
}
pre[p]=nex[p]=0;
}
void work()
{
// int n,k;
memset(f,0,sizeof(f));
memset(b,0,sizeof(b));
read(n);read(k);
for(int i=1;i<=n;i++)
{
read(a[i]);
pos[a[i]]=i;// a[i]
pre[i]=i-1;//
nex[i]=i+1;//
}
LL ans=0;
for(int i=1;i<=n-k+1;i++)// ， 1-n k 1-(n-k+1)
// 1 ， 1 ， 1 ， dele() 1
// 2， 1 ， 2 ， n-k+1
{
int fro=0,beh=0;//front behind
int p=pos[i];
for(int v=p;v&&fro<=k;v=pre[v]) f[fro++]=v;
for(int v=p;v<=n&&beh<=k;v=nex[v]) b[beh++]=v;
f[fro]=0,b[beh]=n+1;
for(int j=0;jbeh-1)
continue;
{
int lnum=f[j]-f[j+1];
int rnum=b[k-1-j+1]-b[k-1-j];
ans+=1ll*i*lnum*rnum;
}
}
dele(p);
}
printf("%lld
",ans);
}
int main()
{
//freopen("1003.in", "r", stdin);
//freopen("data.out", "w", stdout);
int T;
read(T);
while(T--)
{
work();
}
return 0;
}