Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 1269  Solved: 665

[][][]

Description

Input

Output

Sample Input

7 5

0 2 1 0 1 3 2

1 3

2 3

1 4

3 6

2 7

Sample Output

3

0

3

2

4

HINT

 

 

Source

裸地莫队题目，

每次加入一个数，如果当前答案等于加入的数，就暴力向上加

每次删除一个数，如果删除的那个数比当前的答案小，那么当前的答案就赋值程这个数

因此

add和dele函数都非常好些。

但是，，，，，

我写的莫队各种RE，WA，TLE，MLE。。。。。。。。。。。。

和标称拍了一头午也没拍出错误来。。。。

也是醉了。。。

 

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 #include
            
              7 using namespace std; 8 const int MAXN=3000011; 9 /*inline void read(int &n)10 {11 char c='+';int x=0;bool flag=0;12 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}13 while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();14 n=flag==1?-x:x;15 }*/16 const int BUF=30000010;17 char Buf[BUF],*buf=Buf;int BUFflag; 18 inline void read(int &now)19 {20 for(now=0; ! isdigit (*buf); ++buf);21 for(; isdigit ( *buf );now = now * 10+ (*buf-'0') ,++buf);22 }23 struct node24 {25 int l,r,bh,ans;26 }ask[MAXN];27 int n,q;28 int a[MAXN];29 int pos[MAXN];30 int base;31 inline int comp(const node &a,const node &b)32 {33 if(pos[a.l]==pos[a.l]) return pos[a.r]
             
              ll;ll++)60 dele(ll);61 for(;ask[i].r
              
               rr;rr++)64 add(rr+1);65 ask[i].ans=now;66 }67 for(int i=1;i<=q;i++)68 out[ask[i].bh]=ask[i].ans;69 for(int i=1;i<=q;i++)70 printf("%d\n",out[i]);71 }72 int main()73 {74 //freopen("a.in","r",stdin);75 // freopen("b.out","w",stdout);76 fread(buf,1,BUF,stdin);77 read(n);read(q);78 base=sqrt(n);79 for(int i=1;i<=n;i++)80 read(a[i]),pos[i]=(i-1)/base+1;81 for(int i=1;i<=q;i++)82 {83 int ll,rr;read(ll);read(rr);84 ask[i].l=ll;ask[i].r=rr;ask[i].bh=i;85 }86 sort(ask+1,ask+q+1,comp);87 modui();88 return 0;89 }
              
             
            
           
          
         
        
       

1 #include
       
         2 using namespace std; 3 const int maxn = 1000005; 4 inline int read() 5 { 6     int x=0,f=1;char ch=getchar(); 7     while(ch>'9'||ch<'0'){
     if(ch=='-')f=-1;ch=getchar();} 8     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 9     return x*f;10 }11 int a[maxn],pos[maxn],c[maxn],Ans[maxn];12 int ans,n,m;13 struct query14 {15     int l,r,id;16 }Q[maxn];17 bool cmp(query a,query b)18 {19     if(pos[a.l]==pos[b.l])20         return a.r
        
         Q[i].l)L--,Update(a[L]);59         while(R>Q[i].r)Delete(a[R]),R--;60         while(L