算法初探

前言

这篇博客咕咕咕了很久，记得以前还花了整整一上午研究来着

这么简单的东西花一上午唉...

感叹之前的理解能力，果然还是我太弱了

正文

离散化简单来说就是将范围很大，但是不关心具体数值的一列数缩小

举个例子

1 9999999 99998 56 99998

离散化之后就是

1 4 3 2 3

我们要将其按照大小次序排好，必先排序

然后我们去重，否则重复的数会影响lower_bound()函数的正确性

之后顺序查询即可

#include<iostream>
#include<algorithm>
#define N 1000001
using namespace std;
int in[N],n,cnt,st[N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>in[i];
		st[i]=in[i];
	}
	sort(st+1,st+n+1);
	cnt=unique(st+1,st+n+1)-st-1;
	for(int i=1;i<=n;i++){
		in[i]=lower_bound(st+1,st+cnt+1,in[i])-st;
		cout<<in[i]<<" ";
	}
}

CF845C Two TVs

离散化裸题，离散化之后进行区间查询，如果有点的值大于2，不满足题意，输出NO

#include <iostream>
#include <algorithm>
using namespace std;
int n,m,tree[1000001],s[1000001],ls[1000001],num,cnt,nu[1000001];
int lowbit(int a){return a&-a;}
void add(int a,int b){
    while(a<=n*2){
        tree[a]+=b;
        a+=lowbit(a);
    }
}
int search(int a){
    int re=0;
    while(a!=0){
        re+=tree[a];
        a-=lowbit(a);
    }
    return re;
}
int main(){
	ios::sync_with_stdio(0);
	int a,b;
    cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>nu[++num];
    	ls[num]=nu[num];
		cin>>nu[++num];
		ls[num]=nu[num];
	}
    sort(ls+1,ls+2*n+1);
    cnt=unique(ls+1,ls+2*n+1)-ls-1;
    for(int i=1;i<=n;i++){
        	add(lower_bound(ls+1,ls+cnt+1,nu[2*i-1])-ls,1);
        	add(lower_bound(ls+1,ls+cnt+1,nu[2*i])-ls+1,-1);
    }
    for(int i=1;i<=(n<<1);i++){
    	if(search(i)>2){
    		cout<<"NO";
    		return 0;
		}
	}
	cout<<"YES";
}