2021.11.05 eleveni的水省选题的记录

2021.11.05 eleveni的水省选题的记录

因为eleveni比较菜，但是eleveni不想写绿题（总不能说是被绿题虐得不想写），eleveni决定继续水noip原题。

——实际上菜菜的eleveni连noip绿题都不一定能水过/忍不住哭了

[P1966 NOIP2013 提高组] 火柴排队 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本质就是求逆序对的题

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

#include<map>

using namespace std;

//最大对最大？？？WF一道题？？？

#define int long long

const int N=1e6+10;

const int mod=1e8-3;

int n,a[N],b[N],ai[N],bi[N],mapi[N];

int tree[N];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline int lowbit(int x){

	return x&-x;

}

inline void add(int x,int k){

	for(int i=x;i<=n;i+=lowbit(i))tree[i]+=k;

}

inline int query(int x){

	int fin=0;

	for(int i=x;i>0;i-=lowbit(i))fin+=tree[i];

	//cout<<fin;

	return fin;

}

signed main(){

	n=read();

	for(int i=1;i<=n;i++)ai[i]=a[i]=read();

	sort(ai+1,ai+n+1);

	int lena=unique(ai+1,ai+n+1)-ai-1;

	for(int i=1;i<=n;i++)a[i]=lower_bound(ai+1,ai+lena+1,a[i])-ai;

	for(int i=1;i<=n;i++)bi[i]=b[i]=read();

	sort(bi+1,bi+n+1);

	int lenb=unique(bi+1,bi+n+1)-bi-1;

	for(int i=1;i<=n;i++)b[i]=lower_bound(bi+1,bi+lenb+1,b[i])-bi;

	for(int i=1;i<=n;i++)mapi[a[i]]=i,a[i]=i;

	for(int i=1;i<=n;i++)b[i]=mapi[b[i]];

	//for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<endl;

	int ans=0;

	for(int i=n;i>=1;i--){

		ans+=query(b[i]);ans%=mod;

		add(b[i],1);

		//for(int j=1;j<=10;j++)cout<<tree[j]<<"  ";

	}

	cout<<ans;

	return 0;

}

[P3605 USACO17JAN]Promotion Counting P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 #include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=1e5+10;

typedef long long ll;

int n,a[N],ai[N],cnt,head[N],tree[N],ans[N];

struct node{

	int to,next;

}e[N];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline int lowbit(int x){

	return x&-x;

}

inline void addi(int x,int k){

	for(int i=x;i<=n;i+=lowbit(i))tree[i]+=k;

}

inline int query(int x){

	int fin=0;

	for(int i=x;i>0;i-=lowbit(i))fin+=tree[i];

	return fin;

}

inline void add(int u,int v){

	++cnt;

	e[cnt].to=v;

	e[cnt].next=head[u];

	head[u]=cnt;

}

inline void dfs(int x){

	ans[x]-=query(n)-query(a[x]-1);

	for(int i=head[x];i;i=e[i].next){

		int v=e[i].to;

		dfs(v);

	}

	ans[x]+=query(n)-query(a[x]-1);

	addi(a[x],1);

}

int main(){

	n=read();

	for(int i=1;i<=n;i++)ai[i]=a[i]=read();

	sort(ai+1,ai+n+1);

	int len=unique(ai+1,ai+n+1)-ai-1;

	for(int i=1;i<=n;i++)a[i]=lower_bound(ai+1,ai+len+1,a[i])-ai;

	for(int i=2;i<=n;i++){

		int x=read();

		add(x,i);

	}

	dfs(1);

	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;

	return 0;

}

2021.11.05 eleveni的水省选题的记录的相关教程结束。