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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int N=1e6;
int n=read(),m=read(),q=read();
int b[1<<20],qb[1<<20];
ll ans[1<<20];
struct node{int o,t,x,y,p;}a[1<<21],ta[1<<21],tb[1<<21];
const int M=1.6e8;
int head[1<<20],nxt[M],to[M],val[M],cnt;
ll arr[1<<20];
struct DS
{
	ll a[1<<7],b[1<<14],c[1<<20];
	void clr(){memset(a,0,sizeof(a)),memset(b,0,sizeof(b)),memset(c,0,sizeof(c));}
	void add(int x,ll k){a[x>>14]+=k,b[x>>7]+=k,c[x]+=k;}
	ll find(int x)
	{
		int y=x>>7,z=y>>7;
		ll r=0;
		for(int i=(y<<7); i<=x; ++i) r+=c[i];
		for(int i=(z<<7); i<y; ++i) r+=b[i];
		for(int i=0; i<z; ++i) r+=a[i];
		return r;
	}
}Z;
struct DSi
{
	int b[1<<10],a[1<<20];
	void add(int x)
	{
		for(int i=x,j=((i>>10)+1)<<10; i<j; ++i) ++a[i];
		for(int i=(x>>10)+1; i<1024; ++i) ++b[i];
	}
	int find(int x)
	{
		return a[x]+b[x>>10];
	}
}Zi;
void solve(int l,int r)
{
	if(l==r) return ;
	int mid=(l+r)>>1;
	solve(l,mid),solve(mid+1,r);
	int SL=0,SR=0;
	for(int i=l; i<=mid; ++i) if(a[i].o==1) ++SL;
	for(int j=mid+1; j<=r; ++j) if(a[j].o==2) ++SR;
	if(2ll*SL*SR>=n)
	{
		memset(arr,0,(n+1)<<3),Z.clr();
		for(int i=l; i<=mid; ++i) if(a[i].o==1)  arr[a[i].x]+=a[i].y;
		for(int i=n-1; i>=1; --i) arr[i]+=arr[i+1];
		for(int i=0,j=mid+1; j<=r; ++j) if(a[j].o==2) 
		{
			while(i<a[j].x) ++i,Z.add(b[i],arr[i]);
			ans[a[j].p]+=Z.find(a[j].y);
		}
	}
	else if(SL&&SR)
	{
		SL=SR=0;
		for(int i=l; i<=mid; ++i) if(a[i].o==1) ta[++SL]=a[i];
		for(int j=mid+1; j<=r; ++j) if(a[j].o==2) tb[++SR]=a[j];
		for(int i=1; i<=SL; ++i)
			for(int j=1; j<=SR; ++j)
			{
				int d=min(ta[i].x,tb[j].x);
				to[++cnt]=tb[j].p,val[cnt]=ta[i].y,
				nxt[cnt]=head[d],head[d]=cnt;
			}
	}
	int x=l,y=mid+1,z=l;
	while(x<=mid&&y<=r)
		if(a[x].x<a[y].x) ta[z++]=a[x++];
		else ta[z++]=a[y++];
	while(x<=mid) ta[z++]=a[x++];
	while(y<=r) ta[z++]=a[y++];
	for(int i=l; i<=r; ++i) a[i]=ta[i];
	return ;
}
signed main()
{
	for(int i=1; i<=n; ++i) b[i]=N+1-read();
	for(int i=1,j=0,o,x,y; i<=m+q; ++i)
	{
		o=read(),x=read(),y=read();
		if(o==2) y=N+1-y,qb[++j]=y,a[i]=(node){o,i,x,y,j};
		else a[i]=(node){o,i,x,y,0};
	}
	solve(1,m+q);
	for(int i=1; i<=n; ++i)
	{
		Zi.add(b[i]);
		for(int j=head[i]; j; j=nxt[j])
			ans[to[j]]+=1ll*Zi.find(qb[to[j]])*val[j];
	}
	for(int i=1; i<=q; ++i) printf("%lld\n",ans[i]);
	return 0;
}