分块大法好。

将这个颜色序列分成[tex]n^{\frac{1}{3}}[/tex]个块，每个块[tex]n^{\frac{2}{3}}[/tex]个数，预处理出[tex]ans[i][j][k][/tex](表示块[tex]i\rightarrow j[/tex]中，颜色[tex]1\rightarrow k[/tex]的答案)和[tex]cnt[i][j][k][/tex](表示块[tex]i\rightarrow j[/tex]中，颜色[tex]k[/tex]的个数）。这一步复杂度[tex]O(n^{\frac{5}{3}})[/tex]。

询问的时候，将整个询问区间分成左边、中间整块部分以及右边。中间部分直接用[tex]ans[i][j][k][/tex]求答案，左边和右边的答案可以使用一个个将数插入的方法统计(如果原先个数是[tex]cnt[i][j][k][/tex]，插入后[tex]ans+=2*cnt[i][j][k]+1[/tex]，然后[tex]cnt[i][j][k]++[/tex])。统计完后再把数删掉。复杂度[tex]O(qn^{\frac{2}{3}})[/tex]。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#define MAXN 50005
#define MAXM 20005
#define MAXQ 50005
#define MAXB 40
#define BS 1400
long long ans[MAXB][MAXB][MAXM];
long long lastans=0;
int cnt[MAXB][MAXM],cntsum[MAXB][MAXB][MAXM],tcnt[MAXM],inds[MAXB];
int n,q,m,co[MAXN],bcnt=0;
inline bool is_between(int l,int x,int r){return (l<=x&&x<=r);}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++) scanf("%d",&co[i]);
    for(int i=1,ind=1;i<=n;i+=BS,ind++) inds[++bcnt]=i;
    for(int i=1;i<=bcnt;i++) for(int j=inds[i];j<=n&&j<inds[i]+BS;j++) cnt[i][co[j]]++;
    for(int i=1;i<=bcnt;i++)
    {
        memcpy(cntsum[i][i],cnt[i],sizeof(cnt[i]));
        for(int j=i+1;j<=bcnt;j++) for(int k=1;k<=m;k++) cntsum[i][j][k]=cntsum[i][j-1][k]+cnt[j][k];
    }
    for(int i=1;i<=bcnt;i++) for(int j=i;j<=bcnt;j++)
	{
		ans[i][j][0]=0;
		for(int k=1;k<=m;k++) ans[i][j][k]=ans[i][j][k-1]+(long long)cntsum[i][j][k]*cntsum[i][j][k];
	}
    long long l,r,a,b;
    while(q--)
    {
        scanf("%lld%lld%lld%lld",&l,&r,&a,&b);
        l^=lastans,r^=lastans,a^=lastans,b^=lastans;
        long long lb=std::lower_bound(inds+1,inds+bcnt+1,l)-inds,rb=std::upper_bound(inds+1,inds+bcnt+1,r)-inds-1,aa=ans[lb][rb-1][b]-ans[lb][rb-1][a-1];
        if(lb<=rb)
        {
            for(int i=l;i<inds[lb];i++) aa+=is_between(a,co[i],b)?(cntsum[lb][rb-1][co[i]]<<1)+1:0,cntsum[lb][rb-1][co[i]]++;
            for(int i=inds[rb];i<=r;i++) aa+=is_between(a,co[i],b)?(cntsum[lb][rb-1][co[i]]<<1)+1:0,cntsum[lb][rb-1][co[i]]++;
            for(int i=l;i<inds[lb];i++) cntsum[lb][rb-1][co[i]]--;
            for(int i=inds[rb];i<=r;i++) cntsum[lb][rb-1][co[i]]--;
        }
        else
        {
            for(int i=l;i<=r;i++) aa+=is_between(a,co[i],b)?(tcnt[co[i]]<<1)+1:0,tcnt[co[i]]++;
            for(int i=l;i<=r;i++) tcnt[co[i]]--;
        }
        printf("%lld\n",lastans=aa);
    }
    return 0;
}