[bzoj3378][Usaco2004 Open]MooFest 狂欢节_树状数组

2021-07-11 09:05

阅读：516

标签：highlight class add algorithm font string 有一个 return ios

MooFest 狂欢节 bzoj-3378 Usaco-2004 Open

题目大意：给定一个n个数的a序列，每两个数之间有一个距离，两个点之间的权值为$max(a[i],a[j])*dis(i,j)$。

注释：$1\le n\le 2\cdot 10^4$。

想法：裙子说了，这种$max$和$min$的题通常要枚举这个$max$和$min$到底是多少。

这样的话我们就将所有点按权值从大到小排序。

往树状数组里插。

查询直接查询即可。

最后，附上丑陋的代码... ...

#include 
#include 
#include 
#include  
using namespace std;
const int N=20000;
int n,num[N+5],cnt;
long long sum[N+5],ans,tot;
struct Node{int v,x;}a[N+5]; bool cmp(const Node &x,const Node &y){return x.v>y.v;}
inline int lowbit(int x) {return x&(-x);}
void add(int x,int v,int k)
{
    for(int i=x;i0;i-=lowbit(i))
        tot+=sum[i],cnt+=num[i];
}
void work()
{
    for(int i=1;i> n ;
    for(int i=1;i

小结：裙子有时候想法好$nb$啊！%%%

[bzoj3378][Usaco2004 Open]MooFest 狂欢节_树状数组

标签：highlight class add algorithm font string 有一个 return ios

原文地址：https://www.cnblogs.com/ShuraK/p/9551668.html

上一篇：spring boot+mybatis 系列

下一篇：C++——多态实现原理分析

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[bzoj3378][Usaco2004 Open]MooFest 狂欢节_树状数组
文章链接：http://soscw.com/index.php/essay/103631.html

亲，登录后才可以留言！

[bzoj3378][Usaco2004 Open]MooFest 狂欢节_树状数组

评论

热门文章

推荐文章

最新文章

置顶文章