Description

Input

Output

Sample Input

3 4

1 2 2

1 2 1 3

1 2 1 1

1 3 1 3

2 3 2 3

Sample Output

2 2

1 1

3 2

2 1

HINT

N=100000,M=1000000

Solution

首先有一个比较显然的做法就是用莫队加树状数组……然而这样的话复杂度是$n\sqrt nlog$。

因为树状数组的修改和查询都是$log$的，所以我们用一个修改$O(1)$，查询$O(\sqrt n)$的分块代替树状数组，那么总的复杂度就是$n\sqrt n$了。

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define N (100009) 7 #define M (1000009) 8 #define S (359) 9 using namespace std;10 11 int n,m,a[N],l,r,x,y,ans2,Keg[N],q_num;12 int ID[N],L[S],R[S],Val[N][2],Sum[N][2];13 struct Que14 {15     int l,r,a,b,id,ans1,ans2;16     bool operator < (const Que &a) const17     {18         if (ID[l]==ID[a.l]) return r
          
           '9') { if (c=='-') w=-1; c=getchar();}28 while (c>='0' && c<='9') x=x*10+c-'0', c=getchar();29 return x*w;30 }31 32 void Build()33 {34 int unit=sqrt(n);35 int num=n/unit+(n%unit!=0);36 for (int i=1; i<=num; ++i)37 L[i]=(i-1)*unit+1, R[i]=i*unit;38 R[num]=n;39 for (int i=1; i<=num; ++i)40 for (int j=L[i]; j<=R[i]; ++j) ID[j]=i;41 }42 43 int Query(int l,int r,int opt)44 {45 int ans=0;46 if (ID[l]==ID[r])47 {48 for (int i=l; i<=r; ++i) ans+=Val[i][opt];49 return ans;50 }51 for (int i=l; i<=R[ID[l]]; ++i) ans+=Val[i][opt];52 for (int i=L[ID[r]]; i<=r; ++i) ans+=Val[i][opt];53 for (int i=ID[l]+1; i<=ID[r]-1; ++i) ans+=Sum[i][opt];54 return ans;55 }56 57 void Del(int p)58 {59 Val[a[p]][0]--; Sum[ID[a[p]]][0]--;60 if (!Val[a[p]][0]) Val[a[p]][1]--, Sum[ID[a[p]]][1]--;61 }62 63 void Ins(int p)64 {65 Val[a[p]][0]++; Sum[ID[a[p]]][0]++;66 if (Val[a[p]][0]==1) Val[a[p]][1]++, Sum[ID[a[p]]][1]++;67 }68 69 int main()70 {71 n=read(); m=read();72 Build();73 for (int i=1; i<=n; ++i) a[i]=read();74 for (int i=1; i<=m; ++i)75 {76 l=read(); r=read(); x=read(); y=read();77 Q[++q_num]=(Que){l,r,x,y,i};78 }79 sort(Q+1,Q+m+1);80 int l=1,r=0;81 for (int i=1; i<=m; ++i)82 {83 while (l
           
            Q[i].l) Ins(--l);85 while (r
            
             Q[i].r) Del(r--);87 Q[i].ans1=Query(Q[i].a,Q[i].b,0);88 Q[i].ans2=Query(Q[i].a,Q[i].b,1);89 }90 sort(Q+1,Q+m+1,cmp);91 for (int i=1; i<=m; ++i)92 printf("%d %d\n",Q[i].ans1,Q[i].ans2);93 }