#include using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000000000000 template struct segtree{ //元データx[i]はv[n+i] //v[i]の親はv[i/2],子はv[i*2]とv[i*2+1] vector v; int n; const T init_value = 0; segtree(vector &x){ n=1; while(true){ if(n>=x.size())break; n*=2; } v.resize(2*n,init_value); for(int i=0;i=0;i--){ v[i]=func(v[i*2],v[i*2+1]); } } void update(int x,T val){ x+=n; v[x]=val; while(true){ x=(x)/2; v[x]=func(v[x*2],v[x*2+1]); if(x<=0)break; } } //区間[l,r)におけるクエリ処理 T query(int l,int r){ T res = init_value; l+=n;r+=n; while(true){ if(l%2==1){ res=func(v[l],res); l++; } if(r%2==1){ res=func(v[r-1],res); r--; } if(l>=r)break; l/=2;r/=2; } return res; } T func(T a,T b){ return a+b; } void show(){ int n = 1; for(int i=1;i>N>>Q; vector> X; vector ind(N); for(int i=0;i>A; A--; vector x = {i,Inf,A}; X.push_back(x); ind[A]=i; } for(int i=0;i>l; cin>>l>>r; l--;r--; vector a = {l,r,i}; X.push_back(a); } sort(X.begin(),X.end(),greater>()); vector fir(N,0); segtree seg(fir); set S; vector ans(Q); for(int i=0;i