洛谷P1428小鱼比可爱

我就是喜欢分块!!!

我的题库:https://blog.csdn.net/L_Y_T020321/article/details/83152606

首先,先来放一下题面~~占空间~~

题目描述

人比人，气死人；鱼比鱼，难死鱼。小鱼最近参加了一个“比可爱”比赛，比的是每只鱼的可爱程度。参赛的鱼被从左到右排成一排，头都朝向左边，然后每只鱼会得到一个整数数值，表示这只鱼的可爱程度，很显然整数越大，表示这只鱼越可爱，而且任意两只鱼的可爱程度可能一样。由于所有的鱼头都朝向左边，所以每只鱼只能看见在它左边的鱼的可爱程度，它们心里都在计算，在自己的眼力范围内有多少只鱼不如自己可爱呢。请你帮这些可爱但是鱼脑不够用的小鱼们计算一下。

输入输出格式

输入格式：

第一行输入一个整数n，表示鱼的数目。

第二行内输入n个整数，用空格间隔，依次表示从左到右每只小鱼的可爱程度。

输出格式：

行内输出n个整数，用空格间隔，依次表示每只小鱼眼中有多少只鱼不如自己可爱。

输入输出样例

输入样例#1：

6
4 3 0 5 1 2

输出样例#1：

0 0 0 3 1 2

说明

n<=100

有人不解的问:这不就是一道luogu红题么?为毛要分块啊!!

然后,我解释说:这叫作分块中毒综合征

算了,直接上code吧

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int n,N;
int pos[51000],s[51000],tag[51000];
vector<int> v[510];
int query(int x,int y,int c)
{
    int ans=0;
    for (int i=x;i<=min(pos[x]*N,y);i++) 
        if (s[i]+tag[pos[x]]<c) ans++; 
    if (pos[x]!=pos[y])
    {
        for (int i=((pos[y]-1)*N+1);i<=y;i++) if (s[i]+tag[pos[y]]<c) ans++; 
    }
    for (int i=pos[x]+1;i<pos[y];i++)
    {
        int t=c-tag[i];
        ans+=lower_bound(v[i].begin(),v[i].end(),t)-v[i].begin(); 
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    N=sqrt(n);
    for (int i=1;i<=n;i++) scanf("%d",&s[i]);
    for (int i=1;i<=n;i++)
    {
        pos[i]=(i-1)/N+1;
        v[pos[i]].push_back(s[i]);
    }
    for (int i=1;i<=pos[n];i++)
        sort(v[i].begin(),v[i].end());
    for(int i = 1 ; i <= n ; i ++) {
    	cout << query(1,i,s[i]) <<" ";
	}
    return 0;
}

code就不作任何解释了

其实,这道题我的思路就是求枚举每条鱼,找1~i条鱼中所有小与 $a_{i}$ 的个数就好了!!

所以,这道题来做分块最棒了!!!