E - BaoBao Loves Reading ZOJ - 4117 （查询区间内不同数的个数+思维）
题目链接：
E - BaoBao Loves Reading
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。题目大意：有一个书架和桌子，桌子上最多放k本书，然后问你分别当k=i(1<=i<=n)时，顺序看书，如果当前桌子上有书的话，就不用从橱子上拿，如果当前的桌子上满了，会将上一次拿下来的数放上去，然后再取需要的书。然后问你分别当k=i(1<=i<=n)时，需要从书桌上取书多少次。
具体思路：dp[i]表示当k==i时，不需要从书橱上拿书的次数。然后计算答案的时候就是n-dp[i]，代表需要从书橱上拿书的次数。
然后具体计算的时候，看这个样例 4 3 4 2 3 1 4 . 对于第二个4，我们判断这个4和上一次出现4的位置，这段范围内不同的数的个数是多少。对于4来说，这段区间不同的数的个数是2，也就是说当k>=2的时候，这个时候不需要再从书橱上拿书。但是当k<2的时候，是需要从书橱上拿书的。对于每一个位置，我们都这么处理，然后再对dp数组求一遍前缀和就可以了，因为当k==i的时候不需要从书橱上拿书的次数，当k>i的时候，也是肯定不需要拿的。
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 # define inf 0x3f3f3f3f 5 const int maxn = 2e5+100; 6 int pre[maxn]; 7 int tree[maxn]; 8 int dp[maxn]; 9 int n; 10 int lowbit(int t) 11 { 12 return t&-t; 13 } 14 void add(int x,int val) 15 { 16 while(x<=n) 17 { 18 tree[x]+=val; 19 x+=lowbit(x); 20 } 21 } 22 int ask(int x) 23 { 24 int sum=0; 25 while(x) 26 { 27 sum+=tree[x]; 28 x-=lowbit(x); 29 } 30 return sum; 31 } 32 void init() 33 { 34 for(int i=0; i<=n; i++) 35 { 36 pre[i]=0,tree[i]=0,dp[i]=0; 37 } 38 } 39 int main() 40 { 41 int T; 42 scanf("%d",&T); 43 while(T--) 44 { 45 int tmp; 46 scanf("%d",&n); 47 init(); 48 for(int i=1; i<=n; i++) 49 { 50 scanf("%d",&tmp); 51 if(pre[tmp]) 52 { 53 add(pre[tmp],-1); 54 add(i,1); 55 int len=ask(i)-ask(pre[tmp]-1); 56 dp[len]++; 57 pre[tmp]=i; 58 } 59 else 60 { 61 pre[tmp]=i; 62 add(pre[tmp],1); 63 } 64 } 65 for(int i=1; i<=n; i++) 66 { 67 dp[i]+=dp[i-1]; 68 if(i==1) 69 printf("%d",n-dp[i]); 70 else 71 printf(" %d",n-dp[i]); 72 } 73 printf("\n"); 74 } 75 return 0; 76 }
更多精彩
