DifferentIntegers【数状数组求区间不同个数】

Different Integers

题意&＃xff1a;有Q个区间&＃xff0c;问每个区间[L,R]有多少个不同的数字

思路&＃xff1a;BIT

#include
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N&＃61;3e5&＃43;5;
const int MOD&＃61;1e9&＃43;7;
int a[N],tree[N];
template
bool sf(T &ret){ //Faster Inputchar c; int sgn; T bit&＃61;0.1;if(c&＃61;getchar(),c&＃61;&＃61;EOF) return 0;while(c!&＃61;&＃39;-&＃39;&&c!&＃61;&＃39;.&＃39;&&(c<&＃39;0&＃39;||c>&＃39;9&＃39;)) c&＃61;getchar();sgn&＃61;(c&＃61;&＃61;&＃39;-&＃39;)?-1:1;ret&＃61;(c&＃61;&＃61;&＃39;-&＃39;)?0:(c-&＃39;0&＃39;);while(c&＃61;getchar(),c>&＃61;&＃39;0&＃39;&&c<&＃61;&＃39;9&＃39;) ret&＃61;ret*10&＃43;(c-&＃39;0&＃39;);if(c&＃61;&＃61;&＃39; &＃39;||c&＃61;&＃61;&＃39;\n&＃39;){ ret*&＃61;sgn; return 1; }while(c&＃61;getchar(),c>&＃61;&＃39;0&＃39;&&c<&＃61;&＃39;9&＃39;) ret&＃43;&＃61;(c-&＃39;0&＃39;)*bit,bit/&＃61;10;ret*&＃61;sgn;return 1;
}
int ans[N],pre[N],n,q;
struct node{int l,r,id;bool operator <(const node& obj)const{return r}query[N];void add(int x,int v){for(int i&＃61;x;i<&＃61;200000;i&＃43;&＃61;(i&(-i))) tree[i]&＃43;&＃61;v;
}int sum(int pos){int res&＃61;0;for(int i&＃61;pos;i;i-&＃61;(i&(-i))) res&＃43;&＃61;tree[i];return res;
}int main(void){
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);while( (scanf("%d%d",&n,&q))&＃61;&＃61;2){memset(tree,0ll,sizeof tree);memset(pre,0,sizeof pre);memset(ans,0,sizeof ans);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) sf(a[i]),a[i&＃43;n]&＃61;a[i];for(int i&＃61;1;i<&＃61;q;i&＃43;&＃43;){int l,r;sf(l);sf(r);
// if(l&＃61;&＃61;r) query[i].r--;query[i].l&＃61;r,query[i].r&＃61;n&＃43;l;query[i].id&＃61;i;}sort(query&＃43;1,query&＃43;1&＃43;q);int now&＃61;1;for(int i&＃61;1;i<&＃61;q;i&＃43;&＃43;){for(;now<&＃61;query[i].r;now&＃43;&＃43;){if(pre[a[now]]!&＃61;0){add(pre[a[now]],-1);}add(now,1);pre[a[now]]&＃61;now;}ans[query[i].id]&＃61;sum(query[i].r)-sum(query[i].l-1);}for(int i&＃61;1;i<&＃61;q;i&＃43;&＃43;) printf("%d\n",ans[i]);}return 0;
}