hdu 4252 A Famous City (map+rmq)

A Famous CityTime Limit: 10000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1498    Accepted Submission(s): 560

Problem DescriptionInputOutputSample InputSample Output Source#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 100005#define MAXN 100005#define mod 100000007#define INF 0x3f3f3f3f#define pi acos(-1.0)#define eps 1e-6typedef long long ll;using namespace std;int n,m,ans;int a[maxn],f[maxn<<2][20];int dp[maxn];map<int,int>mp;void init_rmq() // 预处理 O(n*log(n)){ int i,j; for(i=1;i<=n;i++) { f[i][0]=a[i]; } for(j=1;(1<<j)<=n;j++) { for(i=1;i+j-1<=n;i++) { f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); } }}int query_rmq(int l,int r){ int k=0; while((1<<(k+1))<=r-l+1) k++; return min(f[l][k],f[r-(1<<k)+1][k]);}void presolve(){ int i,j; mp.clear(); for(i=1;i<=n;i++) { if(!mp[a[i]]) mp[a[i]]=i,dp[i]=0; else { dp[i]=mp[a[i]]; mp[a[i]]=i; } }}void solve(){ int i,j,u,v,val; ans=0; for(i=1;i<=n;i++) { if(a[i]==0) continue ; if(dp[i]==0) ans++; else { u=dp[i],v=i; val=query_rmq(u,v); if(val<a[i]) ans++; } }}int main(){ int i,j,test=0; while(~scanf("%d",&n)) { for(i=1;i<=n;i++) { scanf("%d",&a[i]); } init_rmq(); presolve(); solve(); printf("Case %d: ",++test); printf("%d\n",ans); } return 0;}