题解 - Vijos

6

学习阶段的刘锦钰 LV 9 @ 2018-12-03 16:07:32

送上一好理解+简短的题解

因为这道题的数据范围较小，所以我们可以直接暴力拿到100分：

#include<bits/stdc++.h>
using namespace std;

int n;
int ans1[20000],x[20000],y[20000],ans[20000];

int main()
{
    memset(ans,0,sizeof(ans));
    memset(ans1,0,sizeof(ans1));
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j&&(x[i]>=x[j])&&y[i]>=y[j]) ans[i]++;
    for(int i=1;i<=n;i++)
        ans1[ans[i]]++;
    for(int i=0;i<n;i++)
        printf("%d\n",ans1[i]);
    return 0;
}

同时，如果提高数据范围，我们要怎么办呢？
（抄题解！！！）

我们可以用一种更加高级的做法：树状数组！（妙不可言）
具体可以在网上搜一下

#include<bits/stdc++.h>
using namespace std;
const int N=15005;
int tree[32010];//树状数组
int ans[N];//答案
int lowbit(int k){//找到对应低一级数段
    return k&-k;
}
void add(int k){//在某一点添加
    while(k<32003){
        tree[k]++;
        k+=lowbit(k);
    }
}
int sum(int k){//求和
    int ans=0;
    while(k){
        ans+=tree[k];
        k-=lowbit(k);
    }
    return ans;
}
struct node{
    int x,y;
}nos[N];
bool cmp(node a,node b){
    return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
}
int main(){
    int n;
    cin>>n;
    int i;
    for(i=1;i<=n;i++) cin>>nos[i].x>>nos[i].y;
    sort(nos+1,nos+n+1,cmp);//从小到大排序位置
    tree[1]=0;
    for(i=1;i<=n;i++){//计算答案
        ans[sum(nos[i].y)]++;
        add(nos[i].y);
    }
    for(i=0;i<n;i++) cout<<ans[i]<<endl;
    return 0;
}

zhaozhenhao @ 2018-12-03 16:10:55

可以的可以的
刘锦钰是超神 @ 2018-12-03 16:15:30

写的很好哈哈哈！！！

2

PowderHan LV 10 @ 2016-12-04 08:35:09

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 864 KiB, score = 10
Accepted, time = 0 ms, mem = 864 KiB, score = 100
数据弱啊直接树状数组排序后秒杀~
```
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

char rd; int pn;
template<typename Type>
inline void read(Type& v)
{
pn=1;
while((rd=getchar())<'0'||rd>'9')
if(rd=='-')
pn=-1;
v=rd-'0';
while((rd=getchar())>='0'&&rd<='9')
v=v*10+rd-'0';
v*=pn;
}
template<typename Type>
inline void out(Type v,bool c=1)
{
if(v==0)
putchar(48);
else

{
if(v<0)
{
putchar('-');
v=-v;
}
int len=0,dg[20];
while(v>0)
{
dg[++len]=v%10;
v/=10;
}

for(int i=len;i>=1;i--)
putchar(dg[i]+48);

}
if(c)
putchar('\n');
else
putchar(' ');
}

const int MAXN=15005;
const int MAXV=32005;
struct node
{
int x,y;
bool operator<(const node& b)const
{
if(x==b.x)
return y<b.y;
else
return x<b.x;
}
}a[MAXN];
int t[MAXV];
int ans[MAXN];
int maxy;
int n;

inline int lowbit(int& x)
{
return x&(-x);
}

void init()
{
read(n);
for(int i=1;i<=n;i++)
{
read(a[i].x); read(a[i].y);
maxy=max(maxy,a[i].y);
}
sort(a+1,a+n+1);
}

int sum(int x)
{
int ans=0;
while(x>0)
{
ans+=t[x];
x-=lowbit(x);
}
return ans;
}

void add(int x,int d)
{
while(x<=maxy)
{
t[x]+=d;
x+=lowbit(x);
}
}

void work()
{
for(int i=1;i<=n;i++)
{
ans[sum(a[i].y)]++;
add(a[i].y,1);
}
for(int i=0;i<n;i++)
out(ans[i]);
}

int main()
{
init();
work();
}
```

1

S_Gloria LV 6 @ 2019-10-06 14:47:37

很显然的树状数组

何为树状数组？

写在前面：

原码，反码，补码：

正数：原==反==补

负数：

原码略；

反码：第一位（符号位）不变，其他位取反；

补码：反码+1；

栗子：-10

原码：10001010；

反码：11110101；

补码：11110110；

树状数组：

ccs：树状数组，顾名思义，就是橡树一样的数组..

Description

看这张图就一目了然了。

两个数组：

a[i]储存原序列；
c[i]树状数组；

c[1]存第一个数（如图），
c[2]存前两个数的和，
c[3]存第三个数，
c[4]存前四个数的和...以此类推。

树状数组储存方式独特，其中储存的和的个数为其lowbit值。

举个栗子：

c[1]中存了1个数，lowbit（1）=1；

c[2]中存了2个数，lowbit（2）=2；

c[4]中存了4个数，lowbit（4）=4；

而lowbit怎么算呢？~~（先逃）~~

树状数组主要包括三个函数

first. 求lowbit值

int lowbit(int x)
{
    return x&(-x);
}

second.给第x个数加k

void update(int x,int k)
{

    while(x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}

third.查询区间和

int getsum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

~~（手动模拟一下就知道了）~~

题目

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

输入格式

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3个整数，表示一个操作，具体如下：

操作1：格式：1 x k 含义：将第x个数加上k

操作2：格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式

输出包含若干行整数，即为所有操作2的结果。

#include<iostream>
using namespace std;
int n,m;
int c[510000];
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int k)//对第x个数加k
{

    while(x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}
int getsum(int x)//求前x项的和
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    int a;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        update(i,a);//建立树状数组
    }
        
    int x,k,z;
    
    for(int i=1;i<=m;i++)
    {
        cin>>z>>x>>k;
        if(z==1)update(x,k);
        if(z==2)
        {
            int u=getsum(k);
            int v=getsum(x-1);
            cout<<u-v<<endl; 
        }
    }
}

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数数加上x

2.求出某一个数的值

输入格式

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含2或4个整数，表示一个操作，具体如下：

操作1：格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2：格式：2 x 含义：输出第x个数的值

输出格式

输出包含若干行整数，即为所有操作2的结果。

#include<iostream>
using namespace std;
int n,m;
int c[510000],c2[510000];
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int k)
{

    while(x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    int a,sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        update(i,a);
        sum+=a;
        c2[i]=sum;//直接用前缀和存原树状数组
    }
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        cin>>a;
        if(a==1)
        {
            cin>>x>>y>>z;
            update(x,z);
            update(y+1,-z);
        }
        if(a==2)
        {
            cin>>x;
            cout<<getsum(x)-c2[x-1]<<endl;
        }
    }
}

而这个题就是树状数组的应用，先将坐标从左到右排序，再往里面加点就可以了。

#include<iostream>
#include<algorithm>
using namespace std;
int c[120000],ans[121000];
int n;
struct f
{
    int l,r;
}a[131000];
bool cmp(f x,f y)
{
    if(x.l==y.l)return x.r<y.r;
    else return x.l<y.l;
}
int lowbit(int x)
{
    return x&(-x);
}
void update(int x)
{
    while(x<=35000)
    {
        c[x]++;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].l>>a[i].r;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        ans[getsum(a[i].r)]++;
        update(a[i].r);
        
    }
    for(int i=0;i<n;i++)
        cout<<ans[i]<<endl;
}

1

Zechariah LV 7 @ 2019-01-05 08:53:36

先把所有点按x从小到大排序，这样就只需要y了
枚举每个点，要统计之前有多少个点的y坐标小于等于x，于是考虑树状数组
别忘了查询之后要更新到树上去哦

#include <bits/stdc++.h>
#define lowbit(x) (x&-x)
#define rg register
#define inl inline
typedef long long ll;
typedef unsigned long long ull;
const int N = 4e4 + 10, mod = 1e9 + 7;
using namespace std;
namespace fast_IO {
    ll read()
    {
        rg ll num = 0;
        rg char ch;
        rg bool flag = false;
        while ((ch = getchar()) == ' ' || ch == '\n' || ch == '\r');
        if (ch == EOF)return ch; if (ch == '-')flag = true; else num = ch ^ 48;
        while ((ch = getchar()) != ' '&&ch != '\n'&&ch != '\r'&&~ch)
            num = (num << 1) + (num << 3) + (ch ^ 48);
        if (flag)return -num; return num;
    }
    ll max(rg ll a, rg ll b) { if (a > b)return a; return b; }
    ll min(rg ll a, rg ll b) { if (a < b)return a; return b; }
    void write(rg long long x) { if (x < 0)putchar('-'), x = -x; if (x >= 10)write(x / 10); putchar(x % 10 ^ 48); }
};
struct Node {
    int x, y;
    inl bool operator <(const rg Node &s)const
    {
        return x < s.x || (x == s.x&&y < s.y);
    }
    inl Node() {}
    inl Node(rg int x, rg int y) :x(x), y(y) {}
}p[N];
int c[N], maxn, ans[N], buket[N];
inl void update(rg int x, rg int data)
{
    while (x <= maxn)
    {
        c[x] += data;
        x += lowbit(x);
    }
}
inl int query(rg int x)
{
    rg int ans = 0;
    while (x)
    {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

int main()
{
    rg int n = fast_IO::read();
    for (rg int i = 1; i <= n; ++i)p[i].x = fast_IO::read(),
        maxn = fast_IO::max(maxn, p[i].y = fast_IO::read());
    sort(p + 1, p + n + 1);
    for (rg int i = 1; i <= n; ++i)
    {
        ans[i] = query(p[i].y);
        update(p[i].y, 1);
    }
    for (rg int i = 1; i <= n; ++i)++buket[ans[i]];
    for (rg int i = 0; i != n; ++i)fast_IO::write(buket[i]), putchar('\n');
    return 0;
}

1

Randle LV 9 @ 2017-07-19 09:57:32

不正解：前缀和，死无葬身之所，空间复杂度太高。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<climits>
using namespace std;
const int maxn=20000,inf=INT_MAX;
inline const void read(int &a)
{
a=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=a*10+c-'0';
c=getchar();
}
}
int n,p[maxn],x[maxn],y[maxn],range;
int ans[maxn][maxn],num[maxn];
int main()
{
memset(ans,0,sizeof(ans));
memset(num,0,sizeof(num));
read(n);
for(int i=1;i<=n;i++)
{
read(x[i]);read(y[i]);
range=max(range,max(x[i],y[i]));
ans[x[i]][y[i]]++;
}
for(int i=1;i<=range;i++)
for(int j=1;j<=range;j++)
ans[i][j]=ans[i][j]+ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
for(int i=1;i<=n;i++)num[ans[x[i]][y[i]]-1]++;
for(int i=0;i<=n-1;i++)printf("%d\n",num[i]);
return 0;
}
二维线段树（四叉树）记录每一个区间内的个数，然后统计就是了。不过效率并不高。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
using namespace std;
const int maxn=32001;
inline const void read(int &a)
{
a=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=a*10+c-'0';
c=getchar();
}
}
class node
{
public:
int left,right,up,down,num;
int son1,son2,son3,son4;
void clean()
{
left=right=up=down=num=son1=son2=son3=son4=0;
}
}p[2*maxn];
int n,x[maxn],y[maxn],x_range=0,y_range=0,d=0,ans[maxn];
void build_tree(int i,int o)
{
p[o].num++;
if(p[o].right==p[o].left&&p[o].up==p[o].down)return ;
int midx=(p[o].left+p[o].right)/2,midy=(p[o].up+p[o].down)/2;
if(x[i]<=midx&&y[i]>midy)
{
if(!p[o].son1)

{
d++;
p[o].son1=d;
p[d].left=p[o].left;p[d].right=midx;
p[d].down=midy+1;p[d].up=p[o].up;
}
build_tree(i,p[o].son1);
return ;
}
if(x[i]>midx&&y[i]>midy)
{
if(!p[o].son2)
{
d++;
p[o].son2=d;
p[d].left=midx+1;p[d].right=p[o].right;
p[d].down=midy+1;p[d].up=p[o].up;
}
build_tree(i,p[o].son2);
return ;
}
if(x[i]<=midx&&y[i]<=midy)
{
if(!p[o].son3)

{
d++;
p[o].son3=d;
p[d].left=p[o].left;p[d].right=midx;
p[d].down=p[o].down;p[d].up=midy;
}
build_tree(i,p[o].son3);
return ;
}
if(x[i]>midx&&y[i]<=midy)
{
if(!p[o].son4)

{
d++;
p[o].son4=d;
p[d].left=midx+1;p[d].right=p[o].right;
p[d].down=p[o].down;p[d].up=midy;
}
build_tree(i,p[o].son4);
return ;
}
}
inline const bool intersection(int i,int o)
{
if(p[o].down<=y[i]&&p[o].left<=x[i])return true;
else return false;
}
int find_ans(int i,int o)
{
if(x[i]>=p[o].right&&y[i]>=p[o].up)return p[o].num;
int result=0;
if(p[o].son1&&intersection(i,p[o].son1))result+=find_ans(i,p[o].son1);
if(p[o].son2&&intersection(i,p[o].son2))result+=find_ans(i,p[o].son2);
if(p[o].son3&&intersection(i,p[o].son3))result+=find_ans(i,p[o].son3);
if(p[o].son4&&intersection(i,p[o].son4))result+=find_ans(i,p[o].son4);
return result;
}
int main()
{
memset(ans,0,sizeof(ans));
for(int i=0;i<=2*maxn-1;i++)p[i].clean();
read(n);
for(int i=1;i<=n;i++)
{
read(x[i]);read(y[i]);
x_range=max(x_range,x[i]);y_range=max(y_range,y[i]);
}
p[1].left=1;p[1].right=x_range;p[1].down=1;p[1].up=y_range;d++;
for(int i=1;i<=n;i++)build_tree(i,1);
for(int i=1;i<=n;i++)ans[find_ans(i,1)-1]++;
for(int i=0;i<=n-1;i++)printf("%d\n",ans[i]);
return 0;

}
最终还是要写二维树状数组（此处略）

1

continue; LV 8 @ 2017-05-23 01:29:41

树状数组，妙不可言，学习了

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=15005;
int tree[32010];
int ans[MAXN];
int lowbit(int k){
    return k&-k;
}
void add(int k){
    while(k<32003){
        tree[k]++;
        k+=lowbit(k);
    }
}
int sum(int k){
    int ans=0;
    while(k){
        ans+=tree[k];
        k-=lowbit(k);
    }
    return ans;
}
struct Node{
    int x,y;
}nos[MAXN];
bool cmp(Node a,Node b){
    return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
}
int main(){
    int n;
    cin>>n;
    int i;
    for(i=1;i<=n;i++) cin>>nos[i].x>>nos[i].y;
    sort(nos+1,nos+n+1,cmp);
    tree[1]=0;
    for(i=1;i<=n;i++){
        ans[sum(nos[i].y)]++;
        add(nos[i].y);
    }
    for(i=0;i<n;i++) cout<<ans[i]<<endl;
    return 0;
}

JimmyChen @ 2018-02-04 18:39:00

學習了

0

啡咖啡咖啡咖啡咖 LV 8 @ 2018-08-08 11:48:17

/*树状数组*/
#include<cstdio>
#include<algorithm>
using namespace std;
struct aa
{
    int x,y;
}a[16000];
int n,c[40000],ans[40000],t;
bool cmp(aa p,aa q)
{
    return p.x==q.x?(p.y<q.y):(p.x<q.x);
}
int sum(int x)
{
    int ret=0;
    for(int i=x;i>0;i-=i&-i)
        ret+=c[i];
    return ret;
}
void add(int x)
{
    for(int i=x;i<=32000;i+=i&-i)
        c[i]++; 
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].x==a[i-1].x && a[i].y==a[i-1].y)
        {
            ans[t]++;
            add(a[i].y);
            continue;
        }
        t=sum(a[i].y);
        ans[t]++;
        add(a[i].y);
    }
    for(int i=0;i<n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

0

JimmyChen LV 8 @ 2018-02-04 18:37:43

參考@continue；的解法：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 15000 + 10, MAXY = 32000 + 10;
int n, bit[MAXY], ans[MAXN];

struct point{
    int x, y;
} pt[MAXN];

bool cmp(point p1, point p2){
    return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x;
}

inline int lowbit(int x){return x & -x;}
inline void add(int x){ for (; x <= 32000; x += lowbit(x)) bit[x]++; }
inline int getsum(int x){ int ans = 0; for (;x > 0; x -= lowbit(x)) ans += bit[x]; return ans; }

int main(){
    cin.sync_with_stdio(false); cout.sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> pt[i].x >> pt[i].y;
    }
    sort(pt + 1, pt + 1 + n, cmp);
    for (int i = 1; i <= n; i++){
        ans[getsum(pt[i].y)]++;
        add(pt[i].y);
    }
    for (int i = 0; i < n; i++) cout << ans[i] << endl;
    return 0;
}

0

Zory LV 7 @ 2018-01-08 13:02:44

http://zory.cf/2018-01/弱弱的战壕.html

来源和评测点

Vijos1066

题目

<p id="div-border-top-green">【题目大意】
永恒和mx正在玩一个即时战略游戏，名字嘛~~~~~~恕本人记性不好，忘了。
mx在他的基地附近建立了n个战壕，每个战壕都是一个独立的作战单位，
射程可以达到无限。但是，战壕有一个弱点，就是只能攻击它的左下方，
说白了就是横纵坐标都不大于它的点（mx：“我的战壕为什么这么菜”ToT）。
这样，永恒就可以从别的地方进攻摧毁战壕，从而消灭mx的部队。
战壕都有一个保护范围，同它的攻击范围一样，
它可以保护处在它左下方的战壕。
所有处于它保护范围的战壕都叫做它的保护对象。
这样，永恒就必须找到mx的战壕中保护对象最多的点，从而优先消灭它。
现在，由于永恒没有时间来计算，所以拜托你来完成这个任务：
给出这n个战壕的坐标xi、yi，要你求出保护对象个数为0，1，2……n-1的战壕的个数。

【输入格式】
第一行，一个正整数n（1<=n<=15000）
接下来n行，每行两个数xi,yi，代表第i个点的坐标
（1<=xi,yi<=32000）
注意：可能包含多重战壕的情况（即有数个点在同一坐标）

【输出格式】
输出n行，分别代表保护对象为0，1，2……n-1的战壕的个数。

【输入样例】
5
1 1
5 1
7 1
3 3
5 5

【输出样例】
1
2
1
1
0

</p>

分析

做做难度不大但有所创新的题目还是挺好的
先排序一遍确保形如这样
* -

按顺序处理就保证了y更小
接着用树状数组维护x的前缀和即可

代码

//Zory-2017
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
//*******************全局常量*******************
const int MAXN=15000;
//*******************全局定义*******************
struct pt
{
    int x,y;
}p[MAXN+10];
//*******************接口*******************
int s[32000+10];
int lowbit(int x) {return x&-x;}
void add(int f)
{
    while(f<=32000)
    {
        s[f]+=1;
        f+=lowbit(f);
    }
}
int ask(int r)
{
    int sum=0;
    while(r>0)
    {
        sum+=s[r];
        r-=lowbit(r);
    }
    return sum;
}
//*******************主函数*******************
bool cmp(pt a,pt b)
{
    if(a.y==b.y) return a.x<b.x;
    return a.y<b.y;
    /*
    *  -
     **** *****
    * ***** ***
    */
}
int ans[MAXN+10];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        ans[ask(p[i].x)]++;
        add(p[i].x);
    }
    for(int i=0;i<=n-1;i++) printf("%d\n",ans[i]);
}

0

PowderHan LV 10 @ 2017-05-07 22:26:52

/*
这题数据太弱了？本来想用来练线段树的但是数据太弱直接枚举就好
我就偷个懒了。。反正我也不咋会线段树，但还是说一句以后有时间再来看看
附个线段树代码吧
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct point {
    int x, y;
} _p[15005];
struct Node {
    int l, mid, r;
    int val;
} q[75000];
struct in {
    int x, y, t;
} p[15005];
int n;
int ans[15005];

bool cmp(point a, point b) {
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    if (a.y < b.y)
        return true;
    else
        return false;
}
void initialization(int node, int l, int r) {
    q[node].l = l;
    q[node].mid = (l + r) / 2;
    q[node].r = r;
    if (l == r)
        return ;
    initialization(node * 2, l, q[node].mid);
    initialization(node * 2 + 1, q[node].mid + 1, r);
}
void add(int node, int lr, int val) {
    if (q[node].r == lr && q[node].l == lr) {        
        q[node].val += val;
        return ;
    }
    if (lr <= q[node].mid) {
        add(node * 2, lr, val);
        q[node].val += val;
    }
    else {
        add(node * 2 + 1, lr, val);
        q[node].val += val;
    }
}
int sum(int node, int l, int r) {
    if (q[node].l == l && q[node].r == r) {
        return q[node].val;
    }
    if (r <= q[node].mid)
        return sum(node * 2, l, r);
    if (l <= q[node].mid && q[node].mid < r)
        return (sum(node * 2, l, q[node].mid) + sum(node * 2 + 1, q[node].mid + 1, r));
    if (q[node].mid <= l)
        return (sum(node * 2 + 1, l, r));
}
int main(int argc, const char *argv[]) {
    scanf("%d", &n);
    int maxy = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &_p[i].x, &_p[i].y);
        if (_p[i].y > maxy)
            maxy = _p[i].y;
    }
    sort(_p + 1, _p + n + 1, cmp);
    initialization(1, 1, maxy);
    int tot = 0;
    for (int i = 1; i <= n; ++i) {
        if (_p[i].x != _p[i - 1].x || _p[i].y != _p[i - 1].y) {
            p[++tot].x = _p[i].x;
            p[tot].y = _p[i].y;
            p[tot].t = 1;
        }
        else
            ++p[tot].t;
    }
    for (int i = 1; i <= tot; ++i) {
        add(1, p[i].y, p[i].t);
        ans[sum(1, 1, p[i].y) - 1] += p[i].t;
    }
    for (int i = 0; i < n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}
嗯再来个树状数组的代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,ans[15001],a[32001]={0},maxx=0;
struct poi{
    int x,y;
}p[15001];
bool cmp(const poi &a,const poi &b){
    if(a.y!=b.y)return a.y<b.y;
    else return a.x<b.x;
}
int lowbit(int x){
    return x&(-x);
}
void change(int pos){
    for(int i=pos;i<=32000;i+=lowbit(i))
     a[i]++;
}
int findsum(int pos){
    int sum=0;
    for(;pos>0;pos=pos-lowbit(pos))
    sum+=a[pos];
    return sum;
}
int main(){
    int i,x,y;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d",&p[i].x,&p[i].y);
        maxx=max(maxx,p[i].x);
    }
    sort(p+1,p+n+1,cmp);
    for(i=1;i<=n;i++){
        ans[findsum(p[i].x)]++;
        change(p[i].x);
    }
    for(i=0;i<n;i++)printf("%d\n",ans[i]);
    return 0;
}
然后开始写朴素算法了
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

struct node
{
    int x,y;
}a[15005];
int n;
int ans[15005];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++)
    {
        int tot=0;
        for(int j=1;j<=n;j++)
        {
            if(i==j)
                continue;
            else
                if(a[j].x<=a[i].x&&a[j].y<=a[i].y)
                    tot++;
        }
        ans[tot]++;
    }
    for(int i=0;i<n;i++)
        cout<<ans[i]<<endl;
    return 0;
}

0

陈厚铭 LV 10 @ 2017-05-06 16:20:35

#include <iostream>
#include <algorithm>
using namespace std;
struct point
{
    int x, y;
    void input()
    {
        cin >> x >> y;
    }
};
bool operator < (point a, point b)
{
    if(a.x != b.x)
        return a.x < b.x;
    else
        return a.y < b.y;
}
bool operator == (point a, point b)
{
    return (a.x == b.x) & (a.y == b.y);
}
class node
{
    
private:
    int data;
    int size;
    int num;
    node *left, *right;
    
public:
    node(int x)
    {
        data = x;
        size = 1;
        num = 1;
        left = NULL;
        right = NULL;
    }
    inline void insert(int x)
    {
        size++;
        node *pointer;
        if (x == data)
        {
            num++;
        }
        if (x > data)
        {
            if (right == NULL)
            {
                right = new node(x);
            }
            else
            {
                right->insert(x);
            }
        }
        else if (x < data)
        {
            if (left == NULL)
            {
                left = new node(x);
            }
            else
            {
                left->insert(x);
            }
        }
    }
    inline int search(int x)
    {
        node *pointer;
        int ans = 0;
        if (x >= data)
        {
            ans += num;
            if (left != NULL)
            {
                ans += left->size;
            }
            if (right != NULL)
            {
                ans += right->search(x);
            }
        }
        if (x < data)
        {
            if (left != NULL)
            {
                ans += left->search(x);
            }
        }
        return ans;
    }
};
point p[15100];
int ans[15100];
int main()
{
    int n, tmp;
    int cnt = 1;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        p[i].input();
    }
    sort(p, p + n);
    static node tree(2147483647);
    for (int i = 0; i < n; i++)
    {
        tree.insert(p[i].y);
        if (i < n - 1 && p[i] == p[i + 1])
        {
            cnt++;
        }
        else
        {
            tmp = tree.search(p[i].y);
            ans[tmp] += cnt;
            cnt = 1;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << endl;
    }
    system("pause");
    return 0;
}

先对横坐标排序，手写BST，看每一个点前有多少个横纵坐标都比它小的。
先默认每人都能保护自己，最后全都减一

0

205610760 LV 8 @ 2016-11-17 10:33:39

只能sort＋一维搞。。二维的话炸内存了。。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int N=33000;

vector<pair<int,int> >v;
int n,x,y;

int a[N];
int ans[16000];

void add(int x){
for(int i=x;i<=N;i+=i&(-i))
a[i]++;
}

int ask(int x){
int ret=0;
for(int i=x;i;i-=i&(-i))
ret+=a[i];
return ret;
}

int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&x,&y);
v.push_back(make_pair(x,y));
}
sort(v.begin(),v.end());

for(int i=0;i<n;i++){
ans[ask(v[i].second)]++;
add(v[i].second);
}
for(int i=0;i<n;i++){
printf("%d\n",ans[i]);
}
}

Ximenbao @ 2017-05-06 16:15:20

6
1 4
4 1
3 2
2 1
4 2
2 1
这组数据似乎不对...

0

sxyxsy LV 7 @ 2016-08-21 16:51:14

简粗
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x[15001],y[15001],f[15001]={0},i,j,s;
cin>>n;
for(i=1;i<=n;i++)
cin>>x[i]>>y[i];
for(i=1;i<=n;i++)
{
s=0;
for(j=1;j<=n;j++)
{
if(j==i) continue;
else
if(x[j]<=x[i]&&y[j]<=y[i]) s++;
}
f[s]++;
}
for(i=0;i<=n-1;i++)
cout<<f[i]<<endl;
return 0;
}

0

qig159357 LV 8 @ 2016-05-18 19:40:17

数据超弱～朴素150ms十个点……
```c++
#include<cstdio>
#include<cstring>
using namespace std;

int n;
int ans1[15200],x[15200],y[15200],ans[15200];

int main()
{
memset(ans,0,sizeof(ans));
memset(ans1,0,sizeof(ans1));
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&(x[i]>=x[j])&&y[i]>=y[j]) ans[i]++;
for(int i=1;i<=n;i++)
ans1[ans[i]]++;
for(int i=0;i<n;i++)
printf("%d\n",ans1[i]);
return 0;
}
```

0

dzx123 LV 5 @ 2016-04-18 21:22:59

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,ans[15000];
struct node{int r,l,v;}tr[100001];
struct data{int x,y;}f[15000];

inline bool cmp(data a,data b){return (a.x==b.x)?(a.y<b.y):(a.x<b.x);}

void build(int size,int lf,int rt){
tr[size].v=0;
tr[size].l=lf;
tr[size].r=rt;
if(lf==rt)return;
int mid=(lf+rt)>>1;
build(size<<1,lf,mid);
build(size<<1|1,mid+1,rt);
}

void insert(int st,int ed,int size){
int mid=(tr[size].l+tr[size].r)>>1;
if(tr[size].l==st&&tr[size].r==ed){
tr[size].v++;
return;
}
else if(tr[size].r==tr[size].l)return;
else if(ed<=mid)insert(st,ed,size<<1);
else if(st>mid)insert(st,ed,size<<1|1);
else{
insert(st,mid,size<<1);
insert(mid+1,ed,size<<1|1);
}
}

int query(int x,int size){
if(tr[size].r==tr[size].l)return tr[size].v;
int mid=(tr[size].r+tr[size].l)>>1;
if(x<=mid)return tr[size].v+(query(x,size<<1));
else return tr[size].v+(query(x,size<<1|1));
}

int main(){
cin>>n;
build(1,0,32001);
for(int i=0;i<n;i++){
cin>>f[i].x>>f[i].y;
}
sort(f,f+n,cmp);
for(int i=0;i<n;i++){
ans[query(f[i].y,1)]++;
insert(f[i].y,32001,1);
}
for(int i=0;i<n;i++){
cout<<ans[i]<<"\n";
}
return(0);
}

0

williamking5 LV 8 @ 2016-04-13 23:34:01

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
struct DATA{
    int x;
    DATA (int t){
        x=t;
    }
    DATA (){}
};
bool operator < (const DATA a,const DATA b){
    return a.x<b.x;
}
bool operator > (const DATA a,const DATA b){
    return a.x>b.x;
}
bool operator == (const DATA a,const DATA b){
    return a.x==b.x;
}
bool operator != (const DATA a,const DATA b){
    return a.x!=b.x;
}
struct data_class{
    int HASH;
    DATA data;
    data_class(int h,DATA d){
        HASH=h;data=d;
    }
    data_class(){}
};
bool operator < (const data_class a,const data_class b){
    return (a.data<b.data||a.data==b.data&&a.HASH<b.HASH);
}
bool operator > (const data_class a,const data_class b){
    return (a.data>b.data||a.data==b.data&&a.HASH>b.HASH);
}
bool operator == (const data_class a,const data_class b){
    return a.data==b.data&&a.HASH==b.HASH;
}
bool operator >= (const data_class a,const data_class b){
    return a>b||a==b;
}
struct SBT{
public:
    struct sbt
    {
        int left,right,size;
        data_class data;
    };
    int datacmp(const data_class a,const data_class b){
        if (a.data<b.data) return 1;
        if (a.data>b.data) return -1;
        return 0;
    }
    int top,root;
    sbt* tree;
    SBT(int n){
        top=root=0;
        tree=new sbt[n+10];
        for (int i=0;i<n+10;i++)
            tree[i].left=tree[i].right=tree[i].size=0;
    }
    //如果要维护父亲节点和儿子节点的其他域值则修改adapt
    void adapt(int x){
        tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
    }
    void left_rot(int &x){
        int y=tree[x].right;
        tree[x].right=tree[y].left;
        tree[y].left=x;
        tree[y].size=tree[x].size;
        adapt(x);
        x=y;
    }
    void right_rot(int &x){
        int y=tree[x].left;
        tree[x].left=tree[y].right;
        tree[y].right=x;
        tree[y].size=tree[x].size;
        adapt(x);
        x=y;
    }
    void Maintain(int &x,bool flag){
        if (!flag){
            if (tree[tree[tree[x].left].left].size>tree[tree[x].right].size)
                right_rot(x);
            else
            if (tree[tree[tree[x].left].right].size>tree[tree[x].right].size)
                left_rot(tree[x].left),right_rot(x);
            else
            return;
        }
        else{
            if (tree[tree[tree[x].right].right].size>tree[tree[x].left].size)
                left_rot(x);
            else
            if (tree[tree[tree[x].right].left].size>tree[tree[x].left].size)
                right_rot(tree[x].right),left_rot(x);
            else
            return;
        }
        Maintain(tree[x].left,0);
        Maintain(tree[x].right,1);
        Maintain(x,1);
        Maintain(x,0);
    }
    void insert(int &x,data_class data){
        if (x==0){
            x=++top;
            tree[x].size=1;
            tree[x].left=tree[x].right=0;
            tree[x].data=data;
        }
        else{
            tree[x].size++;
            if (data<tree[x].data) insert(tree[x].left,data);
            else insert(tree[x].right,data);
            Maintain(x,data>=tree[x].data);
        }
    }
    int remove(int fa,int &x,data_class data){
        if (!x) return 0;
        tree[x].size--;
        if (datacmp(data,tree[x].data)==-1)
            remove(x,tree[x].right,data);
        else
        if (datacmp(data,tree[x].data)==1)
            remove(x,tree[x].left,data);
        else{
            if (tree[x].left!=0&&tree[x].right==0){
                tree[x]=tree[tree[x].left];
                return x;
            }
            else
            if (tree[x].right!=0&&tree[x].left==0){
                tree[x]=tree[tree[x].right];
                return x;
            }
            else
            if (tree[x].left==0&&tree[x].right==0){
                if (root==x) root=0;
                if (fa)
                    if (tree[fa].left==x) tree[fa].left=0;
                    else tree[fa].right=0;
            }
            else{
                int ret=tree[x].right;
                while (tree[ret].left)
                    ret=tree[ret].left;
                tree[x].data=tree[ret].data;
                remove(x,tree[x].right,tree[ret].data);
            }
        }
    }
    data_class select(int &x,int k){
        int r=tree[tree[x].left].size+1;
        if (k<r) return select(tree[x].left,k);
        else
        if (k>r) return select(tree[x].right,k-r);
        else
        return tree[x].data;
    }
    int rank(int &x,data_class data){
        if (x==0) return 0;
        if (data>tree[x].data) return tree[tree[x].left].size+1+rank(tree[x].right,data);
        else
        if (data<tree[x].data) return rank(tree[x].left,data);
        else
        return tree[tree[x].left].size+1;
    }
    data_class getmin(){
        int x=root;
        while (tree[x].left) x=tree[x].left;
        return tree[x].data;
    }
    data_class getmax(){
        int x=root;
        while (tree[x].right) x=tree[x].right;
        return tree[x].data;
    }
    //插入一个数
    void Insert(int data){
        insert(root,data_class(top+1,data));
    }
    //删除一个数，在相同的情况下，任意删除其中一个
    void Remove(int data){
        remove(0,root,data_class(0,data));
    }
    //查询第k小的数字
    DATA Select(int k){
        return select(root,k).data;
    }
    //查询比data小（严格）的数字有多少个
    int Rank(int data){
        int result=rank(root,data_class(-1,data));
        return result;
    }
    //查找data是否存在
    bool Find(int data){
        if (!root) return 0;
        else {
            int x=root;
            while (tree[x].data.data!=data&&x){
                if (tree[x].data.data<data) x=tree[x].right;
                else x=tree[x].left;
            }
            if (!x) return 0;
            else if (tree[x].data.data==data) return 1;
        }
    }
    //统计data一共有多少个
    int Count(int data){
        bool exi=Find(data);
        if (exi){
            int aaa=Rank(data);
            int bbb=Rank(data+1);
            return bbb-aaa;
        }
        else return 0;
    }
    //查询最大值
    DATA Getmax(){
        return getmax().data;
    }
    //查询最小值
    DATA Getmin(){
        return getmin().data;
    }
};
SBT a(15020);
struct node{
    int x,y;
} ALL[15020];
bool operator == (const node& a,const node &b){
    return a.x==b.x&&a.y==b.y;
}
int sortcmp(node a,node b){
    return a.x<b.x||a.x==b.x&&a.y<b.y;
}
int num[15020],tmpnum[15020];
int main(){
    int i,j,n;
    scanf("%d",&n);
    for (i=0;i<n;i++)
        scanf("%d%d",&ALL[i].x,&ALL[i].y);
    sort(ALL,ALL+n,sortcmp);

    a.Insert(ALL[0].y);
    int ans=0;
    tmpnum[0]=0;

    for (i=1;i<n;i++){
        int kk=a.Rank(ALL[i].y)+a.Count(ALL[i].y);
        a.Insert(ALL[i].y);
        tmpnum[i]=kk;
    }

    for (i=n-2;i>=0;i--)
        if (ALL[i]==ALL[i+1])
            tmpnum[i]=tmpnum[i+1];

    for (i=0;i<n;i++)
        num[tmpnum[i]]++;
    for (i=0;i<n;i++)
        printf("%d\n",num[i]);
    return 0;
}

shangyuxuan @ 2016-11-10 08:24:37

SBT厉害了word哥

0

hxtis2b LV 10 @ 2016-02-18 09:56:33

#include <iostream>
using namespace std;
int x[5005], y[5005];
int n, k;
int a[5005];
int main(){
cin>>n;
for (int i = 0; i<n; i++)
cin>>x[i]>>y[i];
for (int i = 0; i<n; i++){
k = 0;
for (int j = 0; j < n; j++)
{
if (i != j && x[i] >= x[j] && y[i] >= y[j])
k++;
}
a[k]++;
}
for (int i = 0; i < n; i++)
cout << a[i]<<endl;
return 0;
}

0

zeyong14 LV 8 @ 2015-11-23 20:02:17

树状数组秒过
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <stack>
using namespace std;
inline int LC(int x) {return x << 1;}
inline int RC(int x) {return x << 1 | 1;}
typedef long long LL;
const int N = 15000 + 24;
const int M = 32000 + 24;
int n,m,p,Case = 1,top;
int sum[M];
struct node
{
int x,y;
}s[N];
int k[N];
bool cmp(const node& a, const node& b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int x, int num)
{
while(x <= M)
{
sum[x] += num;
x += lowbit(x);
}
}
int sub(int x)
{
int num = 0;
while(x > 0)
{
num += sum[x];
x -= lowbit(x);
}
return num;
}
int main()
{
#ifdef CDZSC_OFFLINE
freopen("in.txt","r",stdin);
#endif //CDZSC_OFFLINE
while(~scanf("%d",&n))
{
memset(k,0,sizeof(k));
memset(sum,0,sizeof(sum));
for(int i = 0; i < n; i++)
{
scanf("%d%d",&s[i].x,&s[i].y);
}
sort(s,s+n,cmp);
for(int i = 0; i < n; i++)
{
int a = sub(s[i].y);
k[a]++;
add(s[i].y,1);
}
for(int i = 0; i < n; i++)
printf("%d\n",k[i]);
}
}

0

SinceSummer LV 7 @ 2015-11-02 19:27:58

测试数据 #0: Accepted, time = 0 ms, mem = 840 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 832 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 836 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 836 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 836 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 836 KiB, score = 10

测试数据 #6: Accepted, time = 1 ms, mem = 836 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 836 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 832 KiB, score = 10

测试数据 #9: Accepted, time = 6 ms, mem = 836 KiB, score = 10

Accepted, time = 37 ms, mem = 840 KiB, score = 100

数据太小不用离散化，树状数组秒过
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,ans[15001],a[32001]={0},maxx=0;
struct poi{
int x,y;
}p[15001];
bool cmp(const poi &a,const poi &b){
if(a.y!=b.y)return a.y<b.y;
else return a.x<b.x;
}
int lowbit(int x){
return x&(-x);
}
void change(int pos){
for(int i=pos;i<=32000;i+=lowbit(i))
a[i]++;
}
int findsum(int pos){
int sum=0;
for(;pos>0;pos=pos-lowbit(pos))
sum+=a[pos];
return sum;
}
int main(){
int i,x,y;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&p[i].x,&p[i].y);
maxx=max(maxx,p[i].x);
}
sort(p+1,p+n+1,cmp);
for(i=1;i<=n;i++){
ans[findsum(p[i].x)]++;
change(p[i].x);
}
for(i=0;i<n;i++)printf("%d\n",ans[i]);
return 0;
}

0

dllp LV 9 @ 2015-10-30 15:28:05

数据真的弱爆了

题解

214 条题解

写在前面：

树状数组：

树状数组主要包括三个函数

题目

来源和评测点

题目

分析

代码

弱弱的战壕

信息

状态

开发

支持

题解

214 条题解

写在前面：

树状数组：

树状数组主要包括三个函数

题目

来源和评测点

题目

分析

代码

弱弱的战壕

信息

状态

开发

支持

还没有账户？

登录