gjh

gjh
2天前
#include <iostream>

using namespace std;

const int N = 5e5 + 10;

struct node{
int l, r, tmax, lmax, rmax, sum;
}tr[N * 4];

int n, m, a[N];

node merge(node &l,node &r)
{
node p;
p.l = l.l, p.r = l.r;
p.sum = l.sum + r.sum;
p.tmax = max(l.rmax + r.lmax, max(l.tmax, r.tmax));
p.lmax = max(l.lmax, l.sum + r.lmax);
p.rmax = max(r.rmax, r.sum + l.rmax);
return p;
}

void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
tr[u].tmax = max(tr[u << 1].rmax + tr[u << 1 | 1].lmax,max(tr[u << 1].tmax, tr[u << 1 | 1].tmax));
tr[u].lmax = max(tr[u << 1].lmax, tr[u << 1].sum + tr[u << 1 | 1].lmax);
tr[u].rmax = max(tr[u << 1 | 1].rmax, tr[u << 1].rmax + tr[u << 1 | 1].sum);

// printf("从%d到%d 区间和是%d 最大前缀和为%d 最大后缀和为%d 最大区间和为 %d\n", tr[u].l, tr[u].r, tr[u].sum,tr[u].lmax,tr[u].rmax,tr[u].tmax);
}

void build(int u,int l,int r)
{
tr[u] = {l, r};
if (l == r) {
tr[u] = {l, r, a[l], a[l], a[l], a[l]};
}
else {
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}

node query(int u,int l,int r)
{
if (l <= tr[u].l && r >= tr[u].r) return tr[u];

int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else {
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
return merge(left, right);
}
}

void modify(int u,int x,int v)
{
if (tr[u].l == tr[u].r) {
tr[u].lmax = tr[u].rmax = tr[u].sum = tr[u].tmax = v;
}
else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}

void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
build(1, 1, n);
// cout << endl;
for (int i = 1; i <= m; i ++ ){
int op;
int x, y;
cin >> op >> x >> y;
if (op == 1 && x > y) swap(x, y);
if (op == 1) cout << query(1, x, y).tmax << endl;
else modify(1, x, y);
}
}

int main()
{
solve();
}


gjh
2天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define int long long

const int N = 1e5 + 10;

int tr1[N], tr2[N];
int n, m, a[N];

int lowbite(int x) {return x & -x;}

{
for(int i = x; i <= n; i += lowbite(i) )  tr[i] += d;
}

int sum(int tr[],int x)
{
int res = 0;
for (int i = x; i; i -= lowbite(i)) res += tr[i];
return res;
}

int print(int x)
{
return (x + 1) * sum(tr1,x) - sum(tr2,x);
}

signed main()
{
cin >> n >> m;
for (int i = 1; i<= n ; i++  ) cin >> a[i];
for (int i = 1; i <= n; i ++ ) add(tr1,i, a[i] - a[i - 1]);
for (int i = 1; i <= n; i ++ ) add(tr2,i, i * (a[i] - a[i - 1]));
int x = 2;
cout << (x + 1)  * sum(tr1,x) << endl;
cout << sum(tr2,x) << endl;
for (int i = 1; i <= m; i ++ )
{
string op;
int l ,r, d;
cin >> op >> l >> r;
if (op == "C")
{
cin >> d;
add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
}
else
{
cout << print(r) - print(l - 1) << endl;
}
}
}


gjh
2天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2, INT = 0x3f3f3f3f, mod = 1e9 + 7;

#define pi 3.1415926
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;
//ios::sync_with_stdio(false);
ll gcd(ll a,ll b) {return b ? gcd(b, a % b) : a;}
ll qmi(ll a,ll b) {ll res = 1 % b;while (b){if (b & 1) res = (res * a) % mod;a = a * a % mod;b >>= 1;}return res;}

int t, n, m, tr[N], a[N], s[N];

int lowbite(int x) {return x & -x;}

{
for (int i = x; i <= n; i += lowbite(i)) tr[i] += c;
}

int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbite(i)) res += tr[i];
return res;
}

int get(int x)
{
int l = 1, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (sum(mid) >= x) r = mid;
else l = mid + 1;
}
return l;
}

void solve()
{
cin >> n;
for (int i = 2; i <= n; i ++ ) cin >> a[i];

for (int i = 1; i <= n; i ++ ) add(i, 1);

for (int i = n; i; i -- )
{
s[i] = get(a[i] + 1);
}
for (int i = 1; i <= n; i ++ ) cout << s[i] << endl;
}

int main()
{
solve();
}


gjh
4天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2, INT = 0x3f3f3f3f, mod = 1e9 + 7;

#define pi 3.1415926
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;
//ios::sync_with_stdio(false);
ll gcd(ll a,ll b) {return b ? gcd(b, a % b) : a;}
ll qmi(ll a,ll b) {ll res = 1 % b;while (b){if (b & 1) res = (res * a) % mod;a = a * a % mod;b >>= 1;}return res;}

int t, n, m, a[N], tr[N];

int lowbite(int x) {return x & -x;}

{
for (int i = x; i <= n; i += lowbite(i)) tr[i] += c;
}

int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbite(i)) res += tr[i];
return res;
}

void solve()
{
cin >> n >> m;
for (int i = 1; i <= n ; i ++ ) cin >> a[i], add(i,a[i] - a[i - 1]);
for (int i = 1; i <= m; i ++ )
{
string op;
int x, l, r;
cin >> op;
if (op == "Q") {
cin >> x;
cout << sum(x) << endl;
} else {
cin >> l >> r >> x;
}
}
}

int main()
{
solve();
}


gjh
5天前

# include [HTML_REMOVED]

using namespace std;

# define y second

typedef long long ll;
const int N = 2e5 + 10;

int tr[N], n, x, s[N], greator[N], lower[N];

int lowbite(int x) {return x & -x;}

{
for (int i = x; i <= n; i += lowbite(i)) tr[i] += c;
}

int sum(int x)
{
int res = 0;
for (int i = x; i; i -= lowbite(i)) res += tr[i];
return res;
}

void solve()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> s[i];

for (int i = 0; i < n; i ++ )
{
greator[i] = sum(n) - sum(s[i]);
lower[i] = sum(s[i] - 1);
}
memset(tr,0,sizeof tr);
ll res1 = 0, res2 = 0;
for(int i = n - 1; i >= 0; i --)
{

res1 += (ll) (sum(n) - sum(s[i])) * greator[i];
res2 += (ll) sum(s[i] - 1) * lower[i];
}

cout << res1 << ' ' << res2 << endl;


}

int main()
{
solve();
}

gjh
9天前
#include <iostream>

using namespace std;

const int N = 210;

int g[N][N], p[N * N];
int n, m;

int get(int a,int b)
{
return (a - 1) * n + b;
}

void init(int x)
{
for (int i = 1; i <= x;i ++ ) p[i] = i;
}

int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

bool merge(int a,int b)
{
a = find(a), b = find(b);
if (a != b) p[a] = b;
else return true;
return false;
}

int main()
{
cin >> n >> m;
init(n * n);
for (int i = 1; i <= m; i ++ )
{
int x, y, s, t;
char op;
cin >> x >> y >> op;
if (op == 'R') t = get(x, y + 1);
else t = get(x + 1, y);

s = get(x, y);

if (merge(s, t)) {
cout << i << endl;
break;
} else {
if (i == m) cout << "draw" << endl;
}
}
}


gjh
9天前
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int n, m, w;
int f[N];
int c[N], d[N], p[N];

int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

void merge(int a, int b)
{
a = find(a), b = find(b);

if (a != b)
{
p[a] = b;
c[b] += c[a], d[b] += d[a];
}
}

int main()
{
cin >> n >> m >> w;
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 1; i <= n ; i++ )  cin >> c[i] >> d[i];

for (int i = 1; i <= m; i ++ )
{
int a, b;
cin >> a >> b;
merge(a, b);
}

vector<int> q;
q.push_back(0);
for (int i = 1; i <= n; i ++ ) if (p[i] == i) q.push_back(i);

int k = q.size();

for (int i = 1; i < k; i ++ )
{
int j = q[i];
for (int o = w; o >= 0; o -- )
if (c[j] <= o) f[o] = max(f[o], f[o - c[j]] + d[j]);
}
cout << f[w] << endl;
}


gjh
9天前
//
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 2e6 + 10, M = N * 2, INT = 0x3f3f3f3f, mod = 1e9 + 7;

#define pi 3.1415926
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;
//ios::sync_with_stdio(false);
ll gcd(ll a,ll b) {return b ? gcd(b, a % b) : a;}
ll qmi(ll a,ll b) {ll res = 1 % b;while (b){if (b & 1) res = (res * a) % mod;a = a * a % mod;b >>= 1;}return res;}

int t, n, m;
int p[N];

int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

bool solve()
{
vector<pii> q;
map<int,int> book;
int cnt = 1;
scanf("%d", &n);
for (int i = 1; i <= 2 * n; i ++ ) p[i] = i;
for (int i = 1; i <= n ;i ++ )
{
int a, b, e;
scanf("%d%d%d", &a, &b, &e);

if (book[a] == 0) book[a] = cnt ++;
if (book[b] == 0) book[b] = cnt ++;
a = book[a];
b = book[b];
if (e)
{
a = find(a), b = find(b);
if (a != b) p[a] = b;
}
else q.push_back({a, b});
}
for (auto s : q)
{
int a = s.first, b = s.second;
a = find(a), b = find(b);

if (a == b) return false;
}
return true;
}
#include <iostream>
int main()
{
int a;
char b;
char c[4];
double d;
cin >> a >> b >> c >> d;
cout << a << endl << b << endl << c << endl << d;
}


gjh
9天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 1e5 + 10, M = N * 2, INT = 0x3f3f3f3f, mod = 1e9 + 7;

#define pi 3.1415926
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;
//ios::sync_with_stdio(false);
ll gcd(ll a,ll b) {return b ? gcd(b, a % b) : a;}
ll qmi(ll a,ll b) {ll res = 1 % b;while (b){if (b & 1) res = (res * a) % mod;a = a * a % mod;b >>= 1;}return res;}

int t, n, m;
int p[N], d[N];

map<int,int> book;

int find(int x)
{
if (p[x] != x)
{
int root = find(p[x]);
d[x] ^= d[p[x]];
p[x] = root;
}
return p[x];
}

int solve()
{
int cnt = 1;
cin >> n >> m;
for (int i = 1; i <= N; i ++ ) p[i] = i;
for (int i = 0; i < m; i ++ )
{
int a, b;
string op;
cin >> a >> b >> op;
printf("a = %d b = %d ", a, b);
a --;
if (book[a] == 0) book[a] = cnt ++;
if (book[b] == 0) book[b] = cnt ++;
a = book[a], b = book[b];
t = 0;
if (op == "odd") t = 1;

int pa = find(a), pb = find(b);
//printf("pa = %d pb = %d\n", pa, pb);
if (pa == pb) {
printf("d[a] = %d d[b] = %d\n", d[a], d[b]);
if ((d[a] ^ d[b]) != t) return i;
} else {

p[pa] = pb;
d[pa] = d[pa] ^ d[pb] ^ t;
printf("d[pa] = %d\n", d[pa]);
}
}
return m;
}

int main()
{
cout << solve();
}


gjh
9天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30010;

int p[N], d[N], l[N];

void init()
{
for (int i = 1; i < N; i ++ ) p[i] = i, l[i] = i;
}

int find(int x)
{
if (p[x] != x)
{
int root = find(p[x]);
if (d[x]) d[x] += d[p[x]];
else d[x] = d[p[x]] + 1;
p[x] = root;
}

return p[x];
}

void merge(int a,int b)
{
int pa = find(a);
int pb = find(b);
if (pa != pb) {
p[pa] = l[pb];
l[pb] = l[pa];
}
}

int query(int a,int b)
{
int pa = find(a);
int pb = find(b);
if (pa != pb) return -1;
else return abs(d[a] - d[b]) - 1;
}

int main()
{
int n;
cin >> n ;
init();
for (int i = 1; i <= n; i ++ ) {
int a, b;
char op;
cin >> op >> a >> b;
if (op == 'M') merge(a, b);
else cout << query(a, b) << endl;
}
}