宁波网站建设开发多少钱,wordpress 金融 模板下载,网业制作,网页传奇游戏中心https://acm.hdu.edu.cn/showproblem.php?pid7020 题目大意#xff1a;求出区间众数严格大于区间一半大小的子区间的数量。
思路#xff1a;先对每一个数求出对应的位置排列#xff0c;S[j]代表1-有多少个i#xff0c;易得s[r]-s[l]r-l-(s[r]-s[l])的时候子区间{l17020 题目大意求出区间众数严格大于区间一半大小的子区间的数量。
思路先对每一个数求出对应的位置排列S[j]代表1-有多少个i易得s[r]-s[l]r-l-(s[r]-s[l])的时候子区间{l1r}是合法的然后呢我赛时就不知道怎么处理二阶的前缀和数据结构菜鸡。
可以参考P4062 [Code#1]Yazid 的新生舞会
洛谷上的一道一模一样的题
洛谷上的题解https://www.luogu.com.cn/problem/solution/P4062HDU的数据比较大 要n*logn
#include cstdio
#include cstring
#include string
#include cmath
#include iostream
#include algorithm
#include queue
#include cstdlib
#include stack
#include vector
#include set
#include map
#include bitset
#include complex
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define sc second
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pii;
const ll mod1e97;
const ll N 6e610;
const double eps 1e-6;
const double PIacos(-1);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll re(){ll x;scanf(%lld,x);return x;}
int dx[8] {1,0,-1,0,1,1,-1,-1}, dy[8] {0,1,0,-1,1,-1,1,-1};
int n;
int a[N];
vectorintb[N];
ll c1[N],c2[N],c3[N];
ll q(int x){ll ans0;for(int ix;i0;i-lowbit(i)){ansc1[i]*(x2)*(x1)-c2[i]*(2*x3)c3[i];}return ans/2;
}
void add(int x,ll v,int n){//二阶前缀和for(int ix;in;ilowbit(i)){c1[i]v;c2[i]v*x;c3[i]v*x*x;}
}
void solve(){cinn;int maxx0;for(int i1;in;i) {cina[i];maxxmax(maxx,a[i]);b[a[i]].pb(i);}ll ans0;int wcn1;for(int i0;imaxx;i){//if(!b[i].size()) continue;b[i].pb(n1);int last0;for(int j0;jb[i].size();j){int x2*j-(b[i][j]-1)wc;int y2*j-lastwc;ansq(y-1);if(x3) ans-q(x-2);add(x,1,2*n1);add(y1,-1,2*n1);lastb[i][j];}last0;for(int j0;jb[i].size();j){int x2*j-(b[i][j]-1)wc;int y2*j-lastwc;add(x,-1,2*n1);add(y1,1,2*n1);lastb[i][j];}b[i].clear();}coutansendl;
}
int main()
{iosint t;cint;while(t--) solve();return 0;
}
