武汉大学2023年新生程序设计竞赛（同步赛）

#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
*/

#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 _ ^ _;
}