前置知识
解法
单点修改区间查询,但值域巨大,考虑离散化掉 \(x\)。
时刻 \(t\) 仍很大,考虑将其作为 CDQ 分治的第一维,然后套个 CDQ 分治即可,注意及时清空桶数组。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
struct node
{
int pd,pos,val,col,id;
bool operator < (const node &another) const
{
return (pos==another.pos)?(pd>another.pd):(pos<another.pos);
}
}a[300010],tmp[300010];
int b[300010],ans[300010],sum[300010],cnt=0,q_cnt=0;
void add(int pd,int pos,int val,int col,int id)
{
cnt++;
a[cnt].pd=pd;
a[cnt].pos=pos;
a[cnt].val=val;
a[cnt].col=col;
a[cnt].id=id;
}
void cdq(int l,int r)
{
if(l>=r)
{
return;
}
int mid=(l+r)/2,x=l,y=mid+1,pos=l;
cdq(l,mid);
cdq(mid+1,r);
while(x<=mid&&y<=r)
{
if(a[x]<a[y])
{
sum[a[x].col]+=a[x].pd*a[x].val;
tmp[pos]=a[x];
pos++;
x++;
}
else
{
ans[a[y].id]+=a[y].val*sum[a[y].col];
tmp[pos]=a[y];
pos++;
y++;
}
}
while(x<=mid)
{
tmp[pos]=a[x];
pos++;
x++;
}
while(y<=r)
{
ans[a[y].id]+=a[y].val*sum[a[y].col];
tmp[pos]=a[y];
pos++;
y++;
}
for(int i=l;i<=mid;i++)
{
sum[a[i].col]=0;
}
for(int i=l;i<=r;i++)
{
a[i]=tmp[i];
}
}
int main()
{
int n,pd,t,x,i;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>pd>>t>>x;
b[i]=x;
if(pd==1)
{
add(1,t,1,x,0);
}
if(pd==2)
{
add(1,t,-1,x,0);
}
if(pd==3)
{
q_cnt++;
add(0,t,1,x,q_cnt);
}
}
sort(b+1,b+1+n);
b[0]=unique(b+1,b+1+n)-(b+1);
for(i=1;i<=n;i++)
{
a[i].col=lower_bound(b+1,b+1+b[0],a[i].col)-b;
}
cdq(1,cnt);
for(i=1;i<=q_cnt;i++)
{
cout<<ans[i]<<endl;
}
return 0;
}
标签:Little,another,题解,pos,long,mid,Machine,pd,define
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18351458