首页 > 代码库 > CF459D Pashmak and Parmida's problem （树状数组）

CF459D Pashmak and Parmida's problem （树状数组）

2024-07-17 22:30:56   219人阅读

 

Codeforces Round #261 (Div. 2)

 

 

题意：给出数组A，定义f(l,r,x)为A[]的下标l到r之间，等于x的元素数。i和j符合f(1,i,a[i])>f(j,n,a[j])，求i和j的种类数。

题解：使用树状数组统计小于某数的元素数量。

我们可以先把f(1,i,a[i])和f(j,n,a[j])写出来，观察一下，例如样例1：

n=7

A　　1　　2　　1　　1　　2　　2　　1

R　　4　　3　　3　　2　　2　　1　　1

L　　1　　1　　2　　3　　2　　3　　4

其中A为给定的数组，Rj为f(j,n,a[j])，Li为f(1,i,a[i])。

对每个Li，我们要统计的其实就是符合（j>i，且Rj<Li）的Rj的个数。就是这个Li右边有多少个比它小的Rj。

这样我们可以用树状数组，把Rj各个数的数量全存到树状数组里，例如这个样例就是4有1个，3有2个，2有2个，1有2个。然后从左到右遍历Li，每次从树状数组里删掉Rj，并且求sum(Li-1)，也就是树状数组中1~Li-1的和，也就是比Li小的元素个数。

例如这个样例，到L3时，树状数组里记了2个1和2个2（1个4和2个3在之前被删掉了），L3=2，则sum(L3-1)=sum(2)=1的数量+2的数量=3。ans+=3。

核心代码（b和d是map，用来统计元素个数，超碉）：

 1 ll farm(){ 2     int i; 3     ll re=0; 4     b.clear();d.clear(); 5     REPD(i,n){ 6         b[a[i]]++; 7         update(b[a[i]],1); 8     } 9     REP(i,n){10         d[a[i]]++;11         update(b[a[i]],-1);12         b[a[i]]--;13         re+=sum(d[a[i]]-1);14         //cout<<i<<‘ ‘<<d[a[i]]-1<<‘ ‘<<sum(d[a[i]]-1)<<‘ ‘<<re<<endl;15     }16     return re;17 }

 

全代码：

 1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set>10 #include<stack>11 #include<queue>12 using namespace std;13 #define ll long long14 #define usll unsigned ll15 #define mz(array) memset(array, 0, sizeof(array))16 #define minf(array) memset(array, 0x3f, sizeof(array))17 #define REP(i,n) for(i=0;i<(n);i++)18 #define REPD(i,n) for(i=(n)-1;i>=0;i--)19 #define FOR(i,x,n) for(i=(x);i<=(n);i++)20 #define RD(x) scanf("%d",&x)21 #define RD2(x,y) scanf("%d%d",&x,&y)22 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)23 #define WN(x) prllf("%d\n",x);24 #define RE  freopen("D.in","r",stdin)25 #define WE  freopen("1biao.out","w",stdout)26 #define mp make_pair27 const int maxn=1123456;28 ll c[maxn];29 int a[maxn];30 int n;31 32 int lowbit(int x){33     return x&-x;34 }35 36 void update(int x,int y){37     if(!x)return;38     while(x<=n){39         c[x]+=y;40         x+=lowbit(x);41     }42 }43 44 ll sum(int x){45     ll re=0;46     while(x>0){47         re+=c[x];48         x-=lowbit(x);49     }50     return re;51 }52 53 map<int,int> b,d;54 55 ll farm(){56     int i;57     ll re=0;58     b.clear();d.clear();59     REPD(i,n){60         b[a[i]]++;61         update(b[a[i]],1);62     }63     REP(i,n){64         d[a[i]]++;65         update(b[a[i]],-1);66         b[a[i]]--;67         re+=sum(d[a[i]]-1);68         //cout<<i<<‘ ‘<<d[a[i]]-1<<‘ ‘<<sum(d[a[i]]-1)<<‘ ‘<<re<<endl;69     }70     return re;71 }72 73 int main(){74     int i;75     scanf("%d",&n);76     REP(i,n) scanf("%d",&a[i]);77     printf("%I64d\n",farm());78     return 0;79 }
View Code

 


联系
我们