pastebin

Paste poklon, #IE2 -- näytä pelkkänä tekstinä -- uusi tämän pohjalta

Värjäys: Tyyli: ensimmäinen rivinumero: Tabin korvaus: 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
 
const int N=5*100005;
 
struct node{
  int l;
  int r;
  int id;
}u[N];
 
int z;
bool cool(node a,node b)
{
     if(a.l/z<b.l/z)
        return true;
     if(a.l/z>b.l/z)
        return false;
     return a.r<b.r;
}
 map<int,int>cnt;
 int ans[N];
 int v[N];
 
int main()
{
 
     //ios_base:: sync_with_stdio(false); cin.tie(0);
     //freopen("input.in","r",stdin);
        
        int n,q;cin>>n>>q;
        int fuk=0;
        z=sqrt(n);
        
        for(int i=0;i<n;i++)
                scanf("%d",&v[i]);
                    
        for(int i=0;i<q;i++)
        {
             int l,r;
             scanf("%d %d",&l,&r);
             node tmp;
             tmp.l=l-1;
             tmp.r=r-1;
             tmp.id=i;
             u[i]=tmp;
        }
 
         sort(u,u+q,cool);
 
         int st=0,e=0;fuk=0;cnt[v[0]]++;
 
        for(int i=0;i<q;i++)
        {
            int l=u[i].l;
            int r=u[i].r;
           // cout<<l<<" "<<r<<" "<<st<<" "<<e<<" "<<fuk<<endl;
            
            while(st<l)
            {
                cnt[v[st]]--;
                int gg=cnt[v[st]];
                if(gg==1)
                 {fuk--;}
                else if(gg==2){fuk++;}
                 st++;
            }
            while(st>l)
            {
                 st--;
                 cnt[v[st]]++;
                 int gg=cnt[v[st]];
                 if(gg==2)
                 {
                    fuk++;
                 }
                 else if(gg==3)
                 {
                    fuk--;
                 }
            }
            while(e<r)
            {
                e++;
                cnt[v[e]]++;
                int gg=cnt[v[e]];
                if(gg==2)
                {fuk++;}
               else if(gg==3){fuk--;}
            }
            while(e>r)
            {
               cnt[v[e]]--;
               int gg=cnt[v[e]];
               if(gg==1)
               {fuk--;}
               else if(gg==2){fuk++;}
               e--;
            }            
            ans[u[i].id]=fuk;
        }
        
        for(int i=0;i<q;i++)
            printf("%d\n",ans[i]);
 
     return 0;
}