P4390 [BalkanOI2007] Mokia 摩基亚 题解
想必 我的另外一篇题解 已经把这道题的思路说的很清楚了，但是那道题是把所有的修改全部告诉你，然后再一个一个问你矩阵和，但是这道题他是修改中夹着询问，但是没有关系，我们照样可做。
考虑将所有询问或修改存起来，因为我的另外一篇题解的那个思路还支持修改，那我们只需要将所有修改当成那个题里的
但这题的思维难度和代码难度远不止如此，下面说一下要改动的点：
- 这次前缀和数组就只能每个块的处理了，因为如果全部处理，修改时就会产生后面也要修改的情况，这样处理起来就比较麻烦，如果是块前缀和，就只需要对块进行暴力处理就行了。
- 对于每次修改我们要找到当前修改的这个坐标在
a_i 中的位置，这个位置是作为散块的修改位置，因为整块它预处理时使用了排序，所以还得开一个数组记录排序后原本在i 位置的数，现在跑到哪里了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+5;
struct node
{
int x;
int y;
int p;
int id;
}a[N];
int cmp(node x,node y)
{
return x.x == y.x?x.y<y.y:x.x<y.x;
}
struct node1
{
int y;
int p;
int id;
}s[N],s1[N];
int sum[N];
int id[N];
int cmp1(node1 x,node1 y)
{
return x.y<y.y;
}
struct node2
{
int x1;
int y1;
int x2;
int y2;
}e[N];
struct node3
{
int opt;
int x1;
int y1;
int x2;
int y2;
}w[N];
int mpp[N];
int mppp[N];
signed main()
{
int qq = 0;
int _,__,n = 0,m = 0;
scanf("%d %d",&_,&__);
while(1)
{
int opt;
scanf("%d",&opt);
if(opt == 1)
{
int x,y,p;
scanf("%d %d %d",&x,&y,&p);
a[++n] = {x,y,0,n};
w[++qq] = {opt,x,y,p,0};
}
else if(opt == 2)
{
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
e[++m] = {x1,y1,x2,y2};
w[++qq] = {opt,x1,y1,x2,y2};
}
else
{
break;
}
}
int len = sqrt(n);
for(int i = 1;i<=n;i++)
{
id[i] = (i+len-1)/len;
}
sort(a+1,a+n+1,cmp);
for(int i = 1;i<=n;i++)
{
s[i].y = a[i].y;
s[i].p = a[i].p;
s[i].id = i;
s1[i] = s[i];
mpp[a[i].id] = i;
}
for(int i = 1;i<=id[n];i++)
{
int l = (i-1)*len+1,r = min(i*len,n);
sort(s1+l,s1+r+1,cmp1);
sum[l] = s1[l].p;
for(int j = l+1;j<=r;j++)
{
sum[j] = sum[j-1]+s1[i].p;
}
}
for(int i = 1;i<=n;i++)
{
mppp[s1[i].id] = i;
}
int cnt = 0;
for(int i = 1;i<=qq;i++)
{
if(w[i].opt == 1)
{
cnt++;
int tt = mpp[cnt];
int ttt = mppp[tt];
s[tt].p+=w[i].x2;
s1[ttt].p+=w[i].x2;
int l = (id[ttt]-1)*len+1,r = min(id[ttt]*len,n);
sort(s1+l,s1+r+1,cmp1);
sum[l] = s1[l].p;
for(int i = l+1;i<=r;i++)
{
sum[i] = sum[i-1]+s1[i].p;
}
}
else
{
int x1 = w[i].x1,y1 = w[i].y1,x2 = w[i].x2,y2 = w[i].y2;
int l = 1,r = n,num = 0;
while(l<=r)
{
int mid = l+r>>1;
if(a[mid].x>=x1)
{
num = mid;
r = mid-1;
}
else
{
l = mid+1;
}
}
if(!num||a[num].x>x2)
{
printf("0\n");
continue;
}
l = 1,r = n;
int num1 = 0;
while(l<=r)
{
int mid = l+r>>1;
if(a[mid].x<=x2)
{
num1 = mid;
l = mid+1;
}
else
{
r = mid-1;
}
}
if(!num1||a[num1].x<x1)
{
printf("0\n");
continue;
}
int ss = 0;
for(int i = id[num]+1;i<=id[num1]-1;i++)
{
int l = (i-1)*len+1,r = i*len,num2 = 0;
while(l<=r)
{
int mid = l+r>>1;
if(s1[mid].y>=y1)
{
num2 = mid;
r = mid-1;
}
else
{
l = mid+1;
}
}
if(!num2||s1[num2].y>y2)
{
continue;
}
l = (i-1)*len+1,r = i*len;
int num3 = 0;
while(l<=r)
{
int mid = l+r>>1;
if(s1[mid].y<=y2)
{
num3 = mid;
l = mid+1;
}
else
{
r = mid-1;
}
}
if(!num3||s1[num3].y<y1)
{
continue;
}
if(num2 == (i-1)*len+1)
{
ss+=sum[num3];
}
else
{
ss+=sum[num3]-sum[num2-1];
}
}
if(id[num] == id[num1])
{
for(int i = num;i<=num1;i++)
{
if(s[i].y>=y1&&s[i].y<=y2)
{
ss+=s[i].p;
}
}
}
else
{
for(int i = num;i<=id[num]*len;i++)
{
if(s[i].y>=y1&&s[i].y<=y2)
{
ss+=s[i].p;
}
}
for(int i = (id[num1]-1)*len+1;i<=num1;i++)
{
if(s[i].y>=y1&&s[i].y<=y2)
{
ss+=s[i].p;
}
}
}
printf("%d\n",ss);
}
}
return 0;
}提交记录。
这个题还是很有难度的，如果有不会的欢迎私信提问！