记录编号 |
357280 |
评测结果 |
AAAAAAAAAA |
题目名称 |
蝗灾 |
最终得分 |
100 |
用户昵称 |
sxysxy |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
2.927 s |
提交时间 |
2016-12-10 10:20:24 |
内存使用 |
27.25 MiB |
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
using namespace std;
//%%%
namespace IO
{
char buf[1<<18], *fs, *ft;
inline char readc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin), fs==ft))?0:*fs++;
}
inline int fast_read()
{
char c = readc();
int r = 0;
bool sig = false;
while(c > '9' || c < '0')
{
if(c == '-')sig = true;
c = readc();
}
while(c >= '0' && c <= '9')
{
r = (r<<3)+(r<<1)+(c^0x30);
c = readc();
}
return sig?-r:r;
}
}using IO::fast_read;
#define MAXN 500001
typedef long long LL;
struct FenwickTree
{
LL S[MAXN];
int N;
void set_N(int n)
{
N = n;
}
void add(int x, int v)
{
for(; x <= N; x += x&-x)S[x] += v;
}
LL query(int x)
{
LL r = 0;
for(; x; x -= x&-x)
r += S[x];
return r;
}
}fwt;
struct node
{
int id, x, y, v, t;
bool operator<(const node &od)const
{
if(x == od.x && y == od.y)return t < od.t;
if(x == od.x)return y < od.y;
return x < od.x;
}
}q[MAXN], tmp[MAXN];
LL ans[MAXN];
void merge(int l, int r)
{
if(l == r)return;
int m = (l+r)>>1;
for(int i = l; i <= r; i++)
{
if(q[i].id <= m && !q[i].t) //前半段的修改操作
fwt.add(q[i].y, q[i].v);
if(q[i].id > m && q[i].t)
ans[q[i].t] += fwt.query(q[i].y)*q[i].v; //后半段的查询操作
}
for(int i = l; i <= r; i++)
if(q[i].id <= m && !q[i].t)
fwt.add(q[i].y, -q[i].v); //消除操作的影响
int j = l, k = m+1; //merge_sort
for(int i = l; i <= r; i++)
{
if(q[i].id <= m)tmp[j++] = q[i];
else tmp[k++] = q[i];
}
for(int i = l; i <= r; i++)q[i] = tmp[i];
merge(l, m);
merge(m+1, r);
}
int cnt = 0;
int qes = 0;
void insert(int x, int y, int v, int t)
{
q[++cnt] = (node){cnt, x, y, v, t};
}
int W;
int main()
{
//freopen("test_data.txt", "r", stdin);
freopen("locust.in", "r", stdin);
freopen("locust.out", "w", stdout);
W = fast_read();
int m = fast_read();
while(m--)
{
int op = fast_read();
if(op == 1)
{
int x = fast_read();
int y = fast_read();
int v = fast_read();
insert(x, y, v, 0);
}else
{
int x1 = fast_read();
int y1 = fast_read();
int x2 = fast_read();
int y2 = fast_read();
++qes;
insert(x1-1, y1-1, 1, qes);
insert(x1-1, y2, -1, qes);
insert(x2, y1-1, -1, qes);
insert(x2, y2, 1, qes);
}
}
fwt.set_N(W);
sort(q+1, q+cnt+1);
merge(1, cnt);
for(int i = 1; i <= qes; i++)
printf("%lld\n", ans[i]);
return 0;
}