1. 油漆面积

这题的暴力竟然能过。。。 实际上分析时间复杂度是不能过的

先给暴力代码

#include 
using namespace std;
const int N=1e4+10;
bool st[N][N];
int sum;
int n;
int main()
{cin>>n;while(n--){int x,y,x1,y1;cin>>x>>y>>x1>>y1;if(x>x1) swap(x,x1);if(y>y1) swap(y,y1);for(int i=x;i

扫描线加线段树代码 不会做啊待补

#include 
#include 
#include using namespace std;const int N = 1e4 + 10;struct Segment {int x, y1, y2;int k;bool operator < (const Segment &t)const {return x < t.x;}
} seg[N * 2];struct Node {int l, r;int cnt, len;
} tr[N * 4];void pushup(int u) {if (tr[u].cnt > 0)  tr[u].len = tr[u].r - tr[u].l + 1;else if (tr[u].l == tr[u].r)  tr[u].len = 0;else  tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}void build(int u, int l, int r) {tr[u] = {l, r};if (l == r)  return;int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}void modify(int u, int l, int r, int k) {if (tr[u].l >= l && tr[u].r <= r) {tr[u].cnt += k;pushup(u);}else {int mid = tr[u].l + tr[u].r >> 1;if (l <= mid)  modify(u << 1, l, r, k);if (r > mid)   modify(u << 1 | 1, l, r, k);pushup(u);}
}int main() {int n;  scanf("%d", &n);int m = 0;for (int i = 0; i < n; i ++) {int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);seg[m ++] = {x1, y1, y2, 1};seg[m ++] = {x2, y1, y2, -1};}sort(seg, seg + m), build(1, 0, 10000);int res = 0;for (int i = 0; i < m; i ++) {if (i > 0)  res += tr[1].len * (seg[i].x - seg[i - 1]. x);modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].k);}return printf("%d\n", res), 0;
}

但是不知道为什么错了一个点

2. 差分

差分就是基础题

#include 
using namespace std;
const int N=1e5+10;
int s[N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>s[i];for(int i=n;i>=1;i--)s[i]-=s[i-1];while(m--){int l,r,c;cin>>l>>r>>c;s[l]+=c,s[r+1]-=c;}for(int i=1;i<=n;i++){s[i]+=s[i-1];cout<

3. 二维差分

也是一个模板 背过或者简单推一下就好

#include 
using namespace std;
const int N=1010;
int s[N][N];int main()
{int n,m,q;cin>>n>>m>>q;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int x;cin>>x;s[i][j]+=x;s[i+1][j]-=x;s[i][j+1]-=x;s[i+1][j+1]+=x;}while(q--){int x1,y1,x2,y2,c;cin>>x1>>y1>>x2>>y2>>c;s[x1][y1]+=c;s[x1][y2+1]-=c;s[x2+1][y1]-=c;s[x2+1][y2+1]+=c;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cout<