Memory Limit: 256 MB
题目连接 http://codeforces.com/gym/100114Description
The longest road of the Fairy Kingdom has n milestones. A long-established tradition defines a specific color for milestones in each region, with a total of m colors in the kingdom. There is a map describing all milestones and their colors. A number of painter teams are responsible for milestone maintenance and painting. Typically, each team is assigned a road section spanning from milestone #l to milestone #r. When optimizing the assignments, the supervisor often has to determine how many different colors it will take to paint all milestones in the section l…r. Example. Suppose there are five milestones #1, #2, #3, #4, #5 to be painted with colors 1, 2, 3, 2, 1, respectively. In this case, only two different paints are necessary for milestones 2…4: color 2 for milestones #2 and #4, and color 3 for milestone #3. Write a program that, given a map, will be able to handle multiple requests of the kind described above.
Input The first line contains two integers, n and k – the number of milestones and the number of requests, respectively. The second line consists of n integers separated by spaces and defines the sequence of colors for milestones from #1 to #n. The following k lines contain pairs of integers, one pair per line. Each pair consists of two numbers – li and ri – and defines a range of milestones for request i. Output The output file should contain k integers separated by line breaks. Result number i should present the result of the i-th request, i. e. the number of colors required to paint all milestones in the road section li…ri. Sample Input5 3 1 2 3 2 1 1 5 1 3 2 4
Sample Output 3 3 2 HINT 1 ≤ n ≤ 10 000; 1≤ m ≤ 255; 1 ≤ li ≤ ri ≤ n; 1 ≤ k ≤ 100 000.题意
求区间内有多少个不同的数
题解：
离线维护树状数组就好了
代码：
#include <cstdio>#include <cstdlib>#include <sstream>#include <iostream>#include <cmath>#include <cstring>#include <algorithm>#include <string>#include <utility>#include <vector>#include <queue>#include <map>#include <set>using namespace std;typedef long long ll;typedef pair<int,int> PII;#define DEBUG(x) cout<< #x << ':' << x << endl#define FOR(i,s,t) for(int i = (s);i <= (t);i++)#define FORD(i,s,t) for(int i = (s);i >= (t);i--)#define REP(i,n) for(int i=0;i<(n);i++)#define REPD(i,n) for(int i=(n-1);i>=0;i--)#define PII pair<int,int>#define PB push_back#define ft first#define sd second#define lowbit(x) (x&(-x))#define INF (1<<30)#define eps (1e-8)const int maxq = 200011;const int maxn = 30011;int a[maxn],C[maxn],last[1000011];int ans[maxq];void init(){ memset(C,0,sizeof(C)); memset(last,-1,sizeof(last));}struct Query{ int l,r; int idx; bool operator < (const Query & rhs)const{ return r < rhs.r; }}开心的冥王星maxq];void add(int x,int val){ while(x<maxn){ C[xxwdct= val; x += lowbit(x); }}int sum(int x){ int res = 0; while(x > 0){ res += C[x]; x -= lowbit(x); } return res;}int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int n; while(~scanf("%d",&n)){ init(); int q; scanf("%d",&q); FOR(i,1,n)scanf("%d",&a[i]); REP(i,q){ scanf("%d%d",&开心的冥王星i].l,&开心的冥王星i].r); 开心的冥王星i].idx = i; } sort(Q,Q+q); int pre = 1; REP(i,q){ FOR(j,pre,开心的冥王星i].r){ if(last[a[j]]==-1){ add(j,1); }else { add(last[a[j]],-1); add(j,1); } last[a[j]] = j; } ans[开心的冥王星i].idx] = sum(开心的冥王星i].r)-sum(开心的冥王星i].l-1); pre = 开心的冥王星i].r+1; } REP(i,q)printf("%dn",ans[i]); } return 0;}