首页 > 代码库 > HDU 5147 BestCoder #23(树状数组区间 前缀和,后缀和)类似LA4329
HDU 5147 BestCoder #23(树状数组区间 前缀和,后缀和)类似LA4329
类似LA4329
1..n个数字放到n个格子中,求四元组满足(a,b,c,d) a<b<c<d 且 Aa<Ab,Ac<Ad。的个数。
这道题刚开始看就知道要用树状数组去做,起先想的是枚举a,c 这样的话复杂度n^2 必然TLE而且a,c之间大于a的数字也无法统计。
题解:枚举c点。
然后得到c之前满足a,b的数量再乘上比c大的d 的数量就是枚举c此时的数量。这里用了一个子问题的技巧,当枚举c到i点的时候,i-1的情况已知,即存储一个满足a,b在i-1时候的量
然后当到i时候,a,b的取值就再加上比i-1小的数的个数就是了。
小心溢出。
/* *********************************************** Author :bingone Created Time :2014/12/20 18:56:36 File Name :BestCoder23.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> #define inf 0x3f3f3f3f #define maxn (10+60000) #define lowbit(x) (x&-x) using namespace std; typedef long long ll; int N,M,T; int se[maxn]; int getsum(int x) { int res=0; while(x>0){ res+=se[x]; x-=lowbit(x); } return res; } void add(int x) { while(x<=N){ se[x]++; x+=lowbit(x); } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&T); while(T--){ memset(se,0,sizeof(se)); scanf("%d",&N); ll ans=0,pre=0; for(int i=1;i<=N;i++){ int m;scanf("%d",&m); int t=getsum(m); int k=N-m-(i-t-1);//后面比s[i]大的数字 ans+=k*pre; pre+=t; add(m); } printf("%I64d\n",ans); } return 0; }
HDU 5147 BestCoder #23(树状数组区间 前缀和,后缀和)类似LA4329
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。