题目链接:Codeforces 390E Inna and Large Sweet Matrix
题目大意:给出n,m和w,表示在一个n*m的图上进行操作,0表示添加操作,在点(x1,y1)和(x2,y2)之间的所有格子上添加value个糖果;1表示查询操作,查询(x1,y1)和(x2,y2)之间糖果的数量。
解题思路:树状数组,将x,y分开讨论,bit1进行正常的添加操作,bit2则进行周边处理。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 4 * 1000005;
int n[2], w;
ll bit1[2][N], bit2[2][N];
void insert(ll* b, int m, int x, ll value) {
while (x <= m) {
b[x] += value;
x += x & (-x);
}
}
ll get(ll* b, int x) {
ll ans = 0;
while (x > 0) {
ans += b[x];
x -= x & (-x);
}
return ans;
}
ll Get(int id, int r) {
return get(bit1[id], r) * r + get(bit2[id], r);
}
void Insert(int id, int l, int r, ll value) {
insert(bit1[id], n[id], l, value);
insert(bit1[id], n[id], r+1, -value);
insert(bit2[id], n[id], l, -value * (l-1));
insert(bit2[id], n[id], r+1, value * r);
}
int main () {
int x1, x2, y1, y2, v;
scanf("%d%d%d", &n[0], &n[1], &w);
while (w--) {
scanf("%d%d%d%d%d", &v, &x1, &y1, &x2, &y2);
if (v) {
ll ans = Get(1, y2) - Get(1, y1-1) - (Get(0, n[0]) - Get(0, x2) + Get(0, x1-1));
cout << ans << endl;
} else {
ll value;
cin >> value;
Insert(0, x1, x2, value * (y2-y1+1));
Insert(1, y1, y2, value * (x2-x1+1));
}
}
return 0;
}
分享到:
相关推荐
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
打codeforces的神器
codeforces编程网站预测分数插件
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
回头重新看了一下题意,这不就是求最长链的树形dp裸题吗? 代码如下: #include #define ll long long #define inf 0x3f3f3f3f #define mod 1000000007 #define PI acos(-1) #define fi first #define se second #...
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces-177A1-良好矩阵元素 链接: :
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
Codeforces round 678 D2_Codeforces_源码
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
codeforces-js Codeforces JS
Codeforces Round #723 (Div. 2).md