hdu3193 降维+rmq

/* 给定n个数对（p,d），如果有这么一个数对（pi,di），其他所有的数对都不能严格小于这个数对 请求出有多少个这样的数对！ 解法：对于数对（p,d），能找到在【1，p-1]之间的小于d的数对,那么数对（p,d）不符合要求，反之符合 那么开一个数组x，x[i]表示价格不超过p的最小的d的值，rmq打表后即可 */ #include<bits/stdc++.h> using namespace std; #define maxn 10005 struct node{ int p,d; bool operator<(const node & a)const{ if(p==a.p) return d<a.d; return p<a.p; } }a[maxn],ans[maxn]; int dp[maxn][20],x[maxn],n,tot; void ST(){ for(int i=1;i<=10005;i++)dp[i][0]=x[i]; for(int j=1;(1<<j)<=maxn;j++) for(int i=1;i+(1<<j)-1<=maxn;i++) dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } int query(int L,int R){ int k=log2(R-L+1); return min(dp[L][k],dp[R-(1<<k)+1][k]); } int main(){ while(scanf("%d",&n)==1){ for(int i=0;i<10005;i++) x[i]=maxn; for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].p,&a[i].d); a[i].p++;a[i].d++; x[a[i].p]=min(x[a[i].p],a[i].d); } ST();tot=0; for(int i=1;i<=n;i++){ if(a[i].p==1) ans[tot++]=a[i]; else if(a[i].d<=query(1,a[i].p-1)) ans[tot++]=a[i]; } printf("%d\n",tot); sort(ans,ans+tot); for(int i=0;i<tot;i++) printf("%d %d\n",ans[i].p-1,ans[i].d-1); } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10057304.html

相关资源：各显卡算力对照表！