COGS 1260 三元数对
发布日期:2022-02-05 18:27:31 浏览次数:4 分类:技术文章

本文共 2519 字,大约阅读时间需要 8 分钟。

1260. 三元数对

★   输入文件: three.in   输出文件: three.out    简单对比
时间限制:1 s   内存限制:128 MB

【题目描述】

Chineselyl 最近对一种叫做“三元数对”的东西非常感兴趣。在含有 n 个整数的序列 A1,A2,…An 中,三个数被称作“三元数对”当且仅当i<j<k 且 Ai<Aj<Ak 。现在 Chineselyl 正忙着准备会考呢,他想请你帮忙统计一下一个整数序列中“三元数对”的个数。

【输入格式】

* 第一行一个整数 n

* 接下来有 N 行,分别表示这个整数序列的每一项

【输出格式】

 * 输出这个整数序列中三元数对的个数

【样例输入】

512234

【样例输出】

7

【输入输出样例说明】

这7个三元数对分别是

1 2 31 2 41 2 31 2 41 3 42 3 42 3 4

【数据规模】

30%的数据中 n<=100

60%的数据中 n<=2000

100%的数据中 n<=30000 0<=Ai<=maxlongint

注:大规模数据随机生成。





这个题很像那个 COGS  859 数列 但是Ai的范围扩大了 我们只能按n来建树

维护编号是否存在 查询有多少比自己编号小的存在

要事先排序来保证数据的递增/递减性


#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int lim=30011;int sumv[lim<<2];int m,n,a,b,c;struct self{int x,y;}s[lim];long long l[lim],r[lim],z;void pushup(int o){sumv[o]=sumv[o<<1]+sumv[o<<1|1];}int w;int querymin(int o,int l,int r){
        
if(r<=w)return sumv[o];
int m=(l+r)>>1;
int ret=0;
if(w>m)ret+=querymin(o<<1|1,m+1,r);
ret+=querymin(o<<1,l,m);
return ret;}int querymax(int o,int l,int r){
if(l>=w)return sumv[o];
int m=(l+r)>>1;
int ret=0;
if(w<=m)ret+=querymax(o<<1,l,m);
ret+=querymax(o<<1|1,m+1,r);
return ret;}void add(int o,int l,int r){
if(l==r)
{
sumv[o]++;
return;
}
int m=(l+r)>>1;
if(w<=m)add(o<<1,l,m);
else add(o<<1|1,m+1,r);
pushup(o);}int cmp(self a1,self a2){return a1.y
freopen("three.in","r",stdin);
freopen("three.out","w",stdout);
scanf("%d",&m);
for(a=1;a<=m;a++)
{
scanf("%d",&s[a].y);
s[a].x=a;
}
sort(s+1,s+m+1,cmp);
memset(sumv,0,sizeof(sumv));
for(a=1;a<=m;)
{
top=0;
for(b=a;s[b].y==s[a].y;b++)
{
top++;
q[top]=s[b].x;
w=s[b].x-1;
if(w>=1)l[b]=querymin(1,1,m);else l[b]=0;
}
a=b;
for(b=1;b<=top;b++)
{
w=q[b];
add(1,1,m);
}
}
memset(sumv,0,sizeof(sumv));
for(a=m;a>=1;)
{
top=0;
for(b=a;s[b].y==s[a].y;b--)
{
top++;
q[top]=s[b].x;
w=s[b].x+1;
if(w<=m)r[b]=querymax(1,1,m);else r[b]=0;
z+=l[b]*r[b];
}
a=b;
for(b=1;b<=top;b++)
{
w=q[b];
add(1,1,m);
}
}
cout< <
return 0;}


转载地址:https://blog.csdn.net/li412302070/article/details/14000617 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:COGS 859 数列
下一篇:COGS 1266 借教室

发表评论

最新留言

关注你微信了!
[***.191.171.34]2022年08月18日 03时24分10秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章