flandre
做得挺久的，大约做了 \(\rm 1h+\)。
首先，选出来的序列一定是升序的，因为交换升序序列中的任意两个都不可能让「感觉效果」更高。
然后来看选那些数组成这个序列。
接下来是我赛时的想法：
如果全为正数，那么自然正数全部都得选。需要考虑的是负数的情况。
首先，选择一个负数不仅会影响到「真实效果」比它大的烟花的「感觉效果」，比它小的也会影响，两边都有后效性，所以无法通过枚举来动态规划或贪心。
设当前已经选了的序列为 \(c_1,c_2,\dots,c_m\) 且已经有序（升序），那么当判断是否要加入一个新的数 \(c_0\) 时，假如选它不能让总「感觉效果」更大，那么「真实效果」小于等于 \(c_0\) 的更不行（可能的额外「感觉效果」一样，「真实效果」却不大于 \(c_0\)）。
反之，要让「真实效果」小于等于 \(c_0\) 的烟花也能有有效贡献，\(c_0\) 就必须要选，这样才能补齐这些烟花的额外「感觉效果」来让它们有效。
最后，如果选择的序列中间空了一段，那么把这空的一段补齐贡献一定为正，因为这一空段的贡献一定大于已选的较小的一段的贡献，既然那一段都可以选，这一段当然也可以选。
综上所述，在排序后，所选的序列一定是靠右（「真实效果」较大）且连续的。
所以直接从大到小扫描，处理出如果选了 \(a_i\) 所得到的 \(b_i\)（在 \(a\) 值比自己大的所有烟花都被选了的前提下），然后从右往左找最大前缀和即可。
另外，连续相等的不能互相做出贡献，这个要注意。
（因为变量初始化错了 + 可恶的 Subtask 评测方式炸了 \(30\) 分，恶心！）
#include<cstdio>
#include<algorithm>
using namespace std;
namespace IO{
int read()
{
int x=0; bool neg=false;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') neg=true;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return neg?-x:x;
}
int sta[55];
void write_u(unsigned int x)
{
int statop=0;
while(x)
{
sta[++statop]=x%10;
x/=10;
}
while(statop)
putchar('0'+sta[statop--]);
return;
}
}
const int N=1e6+5;
int n;
pair<long long,int> a[N];
long long k,b[N],sum[N];
int main()
{
freopen("flandre.in","r",stdin);
freopen("flandre.out","w",stdout);
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;i++)
{
a[i].first=IO::read();
a[i].second=i;
}
sort(a+1,a+n+1);
int end=n+1; //应当初始化为n+1而非n！（下同）
for(int i=n;i>=1;i--)
{
if(a[i].first!=a[i+1].first) end=i+1;
b[i]=a[i].first+k*(n-end+1);
}
long long mxsum=0; int mxpos=n+1;
for(int i=n;i>=1;i--)
{
sum[i]=sum[i+1]+b[i];
if(sum[i]>mxsum)
{
mxsum=sum[i];
mxpos=i;
}
}
printf("%lld %d\n",mxsum,n-mxpos+1);
for(int i=mxpos;i<=n;i++)
{
IO::write_u(a[i].second);
putchar(' ');
}
return 0;
}
meirin
赛时最后 \(20\) 分钟把 \(40\) 分所需的公式凑出来了，虽然我也不太会证，但还是把我辛辛苦苦凑出来的式子贴在这里：
设 \(f_i\) 表示以 \(i\) 为右端点时的答案（就是题目公式里的 \(r=i\) 时的和），
\[f_i \ = \ f_{i-1} \ + \ a_i \times \sum_{j=1}^{i-1}b_j \ + \ b_i \times \sum_{j=1}^{i-1}a_j \ + \ j \times a_i \times b_i \]答案就是 \(\sum_{i=1}^{n}f_i\)，时间复杂度 \(O(QN)\)。
代码（\(40\) 分）：
点击查看代码
#include<cstdio>
#define updmod(x) x=((x)%P+P)%P
using namespace std;
const int N=5e5+5,P=1000000007;
int n,q,a[N],b[N];
long long f[N];
int main()
{
freopen("meirin.in","r",stdin);
freopen("meirin.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),updmod(a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]),updmod(b[i]);
for(int i=1;i<=q;i++)
{
int pl,pr,pk; scanf("%d%d%d",&pl,&pr,&pk);
for(int j=pl;j<=pr;j++)
b[j]+=pk,updmod(b[j]);
long long ans=0,suma=0,sumb=0;
for(long long j=1;j<=n;j++)
{
f[j]=f[j-1]+a[j]*sumb%P+b[j]*suma%P+j*a[j]%P*b[j]%P; updmod(f[j]);
suma+=j*a[j],sumb=sumb+j*b[j]; updmod(suma),updmod(sumb);
ans+=f[j]; updmod(ans);
}
printf("%lld\n",ans);
}
return 0;
}
正解是数学推式子，但是待定系数那一步我不太能想得到，后面的其实看起来都蛮好推的。
我的代码：
#include<cstdio>
#define updmod(x) x=((x)%P+P)%P
using namespace std;
const int N=5e5+5,P=1000000007;
int n,q,a[N],b[N];
long long prea[N],sufb[N];
long long fl[N],fr[N],f[N],sumf[N];
int main()
{
freopen("meirin.in","r",stdin);
freopen("meirin.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),updmod(a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]),updmod(b[i]);
long long ans=0,suma=0,sumb=0,now=0;
for(long long i=1;i<=n;i++)
{
now+=a[i]*sumb%P+b[i]*suma%P+i*a[i]%P*b[i]%P;
suma=(suma+i*a[i])%P,sumb=(sumb+i*b[i])%P;
ans=(ans+now)%P;
}
for(int i=1;i<=n;i++) prea[i]=(prea[i-1]+1ll*i*a[i])%P;
for(int i=n;i>=1;i--) sufb[i]=(sufb[i+1]+1ll*(n-i+1)*a[i])%P;
for(int i=1;i<=n;i++)
{
fl[i]=((fl[i-1]-prea[i-1])%P+P)%P,fr[i]=(fr[i-1]+sufb[i])%P;
f[i]=(fl[i]+fr[i])%P; sumf[i]=(sumf[i-1]+f[i])%P;
}
for(int i=1;i<=q;i++)
{
int pl,pr,pk; scanf("%d%d%d",&pl,&pr,&pk);
ans+=pk*(sumf[pr]-sumf[pl-1])%P;
updmod(ans); printf("%lld\n",(long long)ans);
}
return 0;
}
sakuya
不会，考场上打的暴力，但是题目数据不讲“入德”，明明说暴力有 \(20\) 分的，结果只有 \(15\) 分，哼
标签：sakuya,NOIP,int,sum,sdis,long,scnt,fa,模拟 From： https://www.cnblogs.com/jerrycyx/p/18528688