记录编号	249880	评测结果	EEEEEEEEEE
题目名称	[SDOI 2009] HH的项链	最终得分	0
用户昵称	asddddd	是否通过	未通过
代码语言	C++	运行时间	1.680 s
提交时间	2016-04-13 20:02:27	内存使用	15.17 MiB

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
#define maxn 51000
#define maxm 210000
using namespace std;
typedef pair<pair<int,int>, pair<int, int> > pi;
int fenwick[maxn],basis[1001000],nextc[1001000],p[1001000];
pi que[maxm];
bool comp(const pi &a,const pi &b){
pair<int, int>tema=a.first;
pair<int, int>temb=b.first;
return tema.first!=temb.first?tema.first<temb.first:tema.second<temb.second;
}
int n,mx;
void addx(int p,int r){
while(p<=n){
fenwick[p]+=r;
p+=(p&-p);
}
return;
}
map<int,int>mapin;
int sum(int p){
int ans=0;
while (p>0) {
ans+=fenwick[p];
p-=p&(-p);
}
return ans;
}
bool comp1(const pi &a,const pi &b){
pair<int, int>tema=a.second;
pair<int, int>temb=b.second;
return tema.first<temb.first;
}
int main() {
freopen("diff.in", "r", stdin);
freopen("diff.out", "w", stdout);
ios::sync_with_stdio(0);
cin>>n;
for (int i=n; i>=1; i--) {
nextc[i]=p[basis[i]];
p[basis[i]]=i;
}
for (int i=1; i<mx; i++) {
if (p[i]) {
addx(p[i], 1);
}
}
int m;
cin>>m;
for (int i=0; i<m; i++) {
int l,r;
cin>>l>>r;
pair<int, int>temp(l,r);
pi asd(temp,pair<int, int>(i,0));
que[i]=asd;
}
int l=1;
sort(que, que+m, comp);
for (int i=0; i<m; i++) {
while (que[i].first.first>l) {
if (nextc[l]) {
addx(nextc[l], 1);
}
l++;
}
que[i].second.second=sum(que[i].first.second)-sum(que[i].first.first-1);
}
sort(que, que+m, comp1);
for (int i=0; i<m; i++) {
cout<<que[i].second.second<<endl;
}
return 0;
}