COGS 1144. [尼伯龙根之歌] 精灵魔法

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

【题目背景】

『谜题在丛林中散发芳香
绿叶上露珠跳跃着歌唱
火焰在隐暗的角落升腾飞起
月华照射着神祇们忠诚的信徒。』

————《瓦尔基里福音书·第六乐章：幻想》————

【题目描述】

Tristan 解决了英灵殿的守卫安排后，便到达了静谧的精灵领地——Alfheim。由于Midgard
处在Alfheim 和冥界Hel 的中间，精灵族领地尚未受到冥界恶灵的侵入。族长Galanodel 为
了帮助米德加尔特抵御外敌，对邪恶亡灵军团使用了高等魔法，从而使得亡灵军团每个士兵
的行进速度变得不一致，从而打乱冥王Hel 安排的最佳阵型。由于这个军团离Midgard 还很
远，因此在抵达Midgard 之前，对于A、B 两个亡灵，若A 的初始位置在B 后面且A 的速
度比B 快，A 就会冲到B 的前面去。现在Galanodel 想知道，会有多少对亡灵之间出现反超
现象？

【输入格式】

第一行一个整数n，表示排成一队的邪恶亡灵军团有多少人。
第二行n 个整数a[i]，表示邪恶亡灵们在数轴上的初始坐标。数据保证这些坐标全部不同。
亡灵军团向数轴正方向前进。
第三行n 个整数v[i]，表示邪恶亡灵们的行进速度。

【输出格式】

一行一个正整数k，表示「反超」的个数。

【样例输入】

复制代码3 1 2 3 2 1 3

1
2
3
3
1 2 3
2 1 3

【样例输出】

复制代码1

1
1

【提示】

Time Limit:1s

对于30%的数据，1<= N<= 1000；
对于100%的数据，1<=N<= 10^5。
所有数据的绝对值均不超过maxlongint。

【来源】

《末世神话：精灵族的急援》

 

线段树 

单点修改，区间查询

按速度排序，每插入一个点之前，寻找比当前亡灵插入早的比他靠前的亡灵累加。

屠龙宝刀点击就送

复制代码#include <algorithm> #include <ctype.h> #include <cstdio> #define N 100005 using namespace std; typedef long long LL; inline void read(LL &x) { register char ch=getchar(); for(x=0;!isdigit(ch);ch=getchar()); for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; } struct Segment { int l,r,mid,val; Segment *ch[2]; Segment() { val=0; ch[0]=ch[1]=NULL; } }*root=new Segment; void build(Segment *&k,int l,int r) { k=new Segment; k->l=l;k->r=r; if(l==r) {k->val=0;return;} k->mid=l+r>>1; build(k->ch[0],l,k->mid); build(k->ch[1],k->mid+1,r); } struct wl { LL pos,v; bool operator<(wl a)const { if(v==a.v) return pos<a.pos; else return v<a.v; } }wl[N]; LL n,ans,Rm; LL query(Segment *&k,int l,int r) { if(k->l==l&&k->r==r) return k->val; if(l>k->mid) return query(k->ch[1],l,r); else if(r<=k->mid) return query(k->ch[0],l,r); else return query(k->ch[0],l,k->mid)+query(k->ch[1],k->mid+1,r); } void change(Segment *&k,int t) { if(k->l==k->r) { k->val++; return; } if(t<=k->mid) change(k->ch[0],t); else change(k->ch[1],t); k->val=k->ch[0]->val+k->ch[1]->val; } int Main() { freopen("alfheim.in","r",stdin); freopen("alfheim.out","w",stdout); read(n); for(int i=1;i<=n;++i) read(wl[i].pos),Rm=max(Rm,wl[i].pos); for(int i=1;i<=n;++i) read(wl[i].v); build(root,1,Rm); sort(wl+1,wl+1+n); for(int i=1;i<=n;++i) { if(wl[i].pos+1<=Rm) ans+=query(root,wl[i].pos+1,Rm); change(root,wl[i].pos); } printf("%lldn",ans); return 0; } int sb=Main(); int main(int argc,char *argv[]) {;}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <algorithm>
#include <ctype.h>
#include <cstdio>
#define N 100005

using namespace std;
typedef long long LL;
inline void read(LL &x)
{
    register char ch=getchar();
    for(x=0;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}
struct Segment
{
    int l,r,mid,val;
    Segment *ch[2];
    Segment()
    {
        val=0;
        ch[0]=ch[1]=NULL;
    }
}*root=new Segment;
void build(Segment *&k,int l,int r)
{
    k=new Segment;
    k->l=l;k->r=r;
    if(l==r) {k->val=0;return;}
    k->mid=l+r>>1;
    build(k->ch[0],l,k->mid);
    build(k->ch[1],k->mid+1,r);
}
struct wl
{
    LL pos,v;
    bool operator<(wl a)const
    {
        if(v==a.v) return pos<a.pos;
        else return v<a.v;
    }
}wl[N];
LL n,ans,Rm;
LL query(Segment *&k,int l,int r)
{
    if(k->l==l&&k->r==r)
        return k->val;
    if(l>k->mid) return query(k->ch[1],l,r);
    else if(r<=k->mid) return query(k->ch[0],l,r);
    else return query(k->ch[0],l,k->mid)+query(k->ch[1],k->mid+1,r);
}
void change(Segment *&k,int t)
{
    if(k->l==k->r)
    {
        k->val++;
        return;
    }
    if(t<=k->mid) change(k->ch[0],t);
    else change(k->ch[1],t);
    k->val=k->ch[0]->val+k->ch[1]->val;
}
int Main()
{
    freopen("alfheim.in","r",stdin);
    freopen("alfheim.out","w",stdout);
    read(n);
    for(int i=1;i<=n;++i) read(wl[i].pos),Rm=max(Rm,wl[i].pos);
    for(int i=1;i<=n;++i) read(wl[i].v);
    build(root,1,Rm);
    sort(wl+1,wl+1+n);
    for(int i=1;i<=n;++i)
    {
        if(wl[i].pos+1<=Rm) ans+=query(root,wl[i].pos+1,Rm);
        change(root,wl[i].pos);
    }
    printf("%lldn",ans);
    return 0;
}
int sb=Main();
int main(int argc,char *argv[]) {;}