显然分块,由于颜色也有区间，我们的ans[l,r,k]表示块l和块r颜色1~k的权值和
所以我们块的大小要设为n^(2/3)，其它没什么说的，比较水
1 var f:array[0..41,0..41,0..20005] of int64; 2 g:array[0..41,0..20005] of longint; 3 s:array[0..20005] of longint; 4 a,be,q:array[0..50010] of longint; 5 ans,size,t,tot,i,l,r,n,m,te,x,y:longint; 6 7 procedure swap(var a,b:longint); 8 var c:longint; 9 begin 10 c:=a; 11 a:=b; 12 b:=c; 13 end; 14 15 procedure prework; 16 var i,j,k:longint; 17 begin 18 for i:=1 to n do 19 inc(g[be[i],a[i]]); 20 for i:=2 to t do 21 for j:=1 to m do 22 g[i,j]:=g[i-1,j]+g[i,j]; 23 for i:=1 to t do 24 begin 25 for j:=(i-1)*size+1 to n do 26 begin 27 if j mod size=1 then 28 begin 29 for k:=1 to m do 30 f[i,be[j],k]:=f[i,be[j]-1,k]; 31 end; 32 inc(f[i,be[j],a[j]],s[a[j]]*2+1); 33 inc(s[a[j]]); 34 end; 35 for j:=i to t do 36 for k:=1 to m do 37 inc(f[i,j,k],f[i,j,k-1]); 38 fillchar(s,sizeof(s),0); 39 end; 40 end; 41 42 procedure clear; 43 var i:longint; 44 begin 45 for i:=1 to tot do 46 s[q[i]]:=0; 47 end; 48 49 function ask(l,r,x,y:longint):int64; 50 var i:longint; 51 begin 52 tot:=0; 53 ask:=0; 54 if be[l]=be[r] then 55 begin 56 for i:=l to r do 57 if (a[i]>=x) and (a[i]<=y) then 58 begin 59 if s[a[i]]=0 then 60 begin 61 inc(tot); 62 q[tot]:=a[i]; 63 end; 64 ask:=ask+s[a[i]]*2+1; 65 inc(s[a[i]]); 66 end; 67 clear; 68 end 69 else begin 70 ask:=f[be[l]+1,be[r]-1,y]-f[be[l]+1,be[r]-1,x-1]; 71 for i:=l to be[l]*size do 72 if (a[i]>=x) and (a[i]<=y) then 73 begin 74 if s[a[i]]=0 then 75 begin 76 inc(tot); 77 q[tot]:=a[i]; 78 s[a[i]]:=g[be[r]-1,a[i]]-g[be[l],a[i]]; 79 end; 80 ask:=ask+s[a[i]]*2+1; 81 inc(s[a[i]]); 82 end; 83 for i:=(be[r]-1)*size+1 to r do 84 if (a[i]>=x) and (a[i]<=y) then 85 begin 86 if s[a[i]]=0 then 87 begin 88 inc(tot); 89 q[tot]:=a[i]; 90 s[a[i]]:=g[be[r]-1,a[i]]-g[be[l],a[i]]; 91 end; 92 ask:=ask+s[a[i]]*2+1; 93 inc(s[a[i]]); 94 end; 95 clear; 96 end; 97 end; 98 99 begin100 readln(n,m,te);101 size:=1;102 while size*size/n*size0 then inc(t);111 prework;112 for i:=1 to te do113 begin114 readln(l,r,x,y);115 l:=l xor ans;116 r:=r xor ans;117 x:=x xor ans;118 y:=y xor ans;119 if l>r then swap(l,r);120 if x>y then swap(x,y);121 ans:=ask(l,r,x,y);122 writeln(ans);123 end;124 end.