C. 覆叶之交（线段树+离散化+扫描线）
输入格式：
输出格式：
输入
0 0 2 3
0 0 3 2
-1 -1 1 1
输出
11
说明
线段树+离散化+扫描线
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define lowbit(ver) ver&(-ver)
#define pii pair<int,int>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define ull unsigned long long
// #define int long long
#define int __int128
#define eps 1e-9
#define pb push_back
#define mod1 1000000007
#define mod2 998244353
#define endl "\n"
#define YES "YES\n"
#define NO "NO\n"
#define Yes "Yes\n"
#define No "No\n"
#define yes "yes\n"
#define no "no\n"
#define fi first
#define se second
using namespace std;
typedef __int128 i64;
const int N = 2e5 + 10;
int n;
inline i64 Read(){
i64 x=0,f=1;char c=getchar();//isdigit
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x * f;
}
inline void Write(int x){
if(x < 0){putchar('-');x=-x;}
if(x>9)Write(x/10);putchar(x%10+'0');
return;
}
inline void Write(int x, char c){
Write(x), putchar(c);
}
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;
int len;
}tr[N * 8];
vector<int> ys;
int find(int y)
{
return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}
void pushup(int u)
{
if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
else if (tr[u].l != tr[u].r)
{
tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}
else tr[u].len = 0;
}
void build(int u, int l, int r)
{
tr[u] = {l, r, 0, 0};
if (l != r)
{
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);
}
}
void solve()
{
n = 3;
for (int i = 0, j = 0; i < n; i ++ )
{
int x1, y1, x2, y2;
x1 = Read();
y1 = Read();
x2 = Read();
y2 = Read();
seg[j ++ ] = {x1, y1, y2, 1};
seg[j ++ ] = {x2, y1, y2, -1};
ys.push_back(y1), ys.push_back(y2);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
build(1, 0, ys.size() - 2);
sort(seg, seg + n * 2);
int ans = 0;
for (int i = 0; i < n * 2; i ++ )
{
if (i > 0) ans += tr[1].len * (seg[i].x - seg[i - 1].x);
modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
}
Write(ans);
// printf("%.0lf\n\n", res * eps * eps);
}
signed main(){
IOS; int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}
/*
100000 100000 -100000000 -10000000
-1000000 -10000000 10000000 -100000
-1000000 1000000 -1000000000 -100000000
1000000000 0 -1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
-1000000000 1000000000 1000000000 1000000000
*/
J. 放棋子（模拟orDP）
输入格式：
输出格式：
输入
3 3
.#.
.#.
输出
32
说明
点击查看代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define int long long
using namespace std;
typedef __int128 i64;
const int N = 2e5 + 10;
int a[N], b[N], f[N];
int ans;
int n, m;
inline i64 Read(){
i64 x=0,f=1;char c=getchar();//isdigit
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x * f;
}
inline void Write(int x){
if(x < 0){putchar('-');x=-x;}
if(x>9)Write(x/10);putchar(x%10+'0');
return;
}
inline void Write(int x, char c){
Write(x), putchar(c);
}
void solve()
{
cin >> n >> m;
int ans = 0, t = 0, f = 1;
string s[n];
for(int i = 0; i < n; i ++)
cin >> s[i];
for(int i = 0; i < n; i ++)
{
f = 0;
for(int j = 0; j < m; j ++)
{
if(s[i][j] == '#')
{
f ++;
ans += f * f;
}
else f = 0;
}
}
for(int i = 0; i < m; i ++)
{
f = 0;
for(int j = 0; j < n; j ++)
{
if(s[j][i] == '#')
{
f ++;
ans += f * f;
}
else f = 0;
}
}
cout << ans << '\n';
}
signed main(){
IOS; int _ = 1;
// cin >> _;
while(_ --)
solve();
return _ ^ _;
}