codeforces 742

contents：

• A。
• B。MEXor Mixup
• C.
• D.
• E.

A。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1E5 + 7;
int n, t;
string s;

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        cin >> s;
        string t = "";
        for (int i = 0; i < n; i++)
        {
            if (s[i] == 'L' || s[i] == 'R')
                t += s[i];
            else if (s[i] == 'U')
                t += 'D';
            else
                t += 'U';
        }
        cout << t << endl;
    }
}

B。MEXor Mixup

题意

一个数组满足一个条件
最小的mxa=a
数组XOR值为b

思路

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;

int T;
int v[N];

int main()
{
    for (int i = 1; i < N; ++i)
        v[i] = v[i - 1] ^ i;
    cin >> T;
    while (T--)
    {
        int a, b;
        cin >> a >> b;
        b ^= v[a - 1];
        if (b == 0)
            cout << a << endl;
        else if (b == a)
            cout << a + 2 << endl;
        else
            cout << a + 1 << endl;
    }
}

C.

AC代码

#include <bits/stdc++.h>

using namespace std;

int n;
char s[15];

int main()
{
	int T;
	scanf ("%d", &T);
	while (T--)
	{
		scanf ("%s", s + 1); n = strlen(s + 1);
		int a = 0, b = 0;
		for (int i = 1; i <= n; i++)
		if (i & 1) a = a * 10 + (s[i] - '0');
		else b = b * 10 + (s[i] - '0');
		printf ("%lld\n", 1ll * (a + 1) * (b + 1) - 2);
	}
	return 0;
}

D.

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
    ll n,s;

    cin>>s>>n;
    while(n>0)
    {
        if(n==1){cout<<s<<endl;break;}
        ll u=1000000000;
        while(s-u<n-1)u/=10;
        cout<<u<<" ";
        s-=u;
        n--;
    }
}
    return 0;

}

E.

AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int N, Q;

int A[202020];

struct Node {
	int ln, rn, len, lv, rv;
	ll x;

	Node() : ln(0), rn(0), len(0), lv(1010101010), rv(0), x(0) {}
	Node(int v) : ln(1), rn(1), len(1), lv(v), rv(v), x(1) {}

	Node operator+ (const Node& o) const {
		Node ret;
		ret.len = len + o.len;
		ret.lv = lv; ret.rv = o.rv;
		ret.x = x + o.x;
		if(ln < len || rv > o.lv) ret.ln = ln;
		else ret.ln = ln + o.ln;
		if(o.rn < o.len || o.lv < rv) ret.rn = o.rn;
		else ret.rn = o.rn + rn;
		if(rv <= o.lv) ret.x += (ll)rn * o.ln;
		return ret;
	}
};

struct SegTree {
	Node T[4 * 202020];

	void upd(int idx, int s, int e, int p, int x) {
		if(p < s || e < p) return;
		if(s == e) {
			T[idx] = Node(x);
			return;
		}
		int m = s + e >> 1;
		upd(idx << 1, s, m, p, x);
		upd(idx << 1 | 1, m + 1, e, p, x);
		T[idx] = T[idx << 1] + T[idx << 1 | 1];
	}

	Node get(int idx, int s, int e, int p, int q) {
		if(q < p || q < s || e < p) return Node();
		if(p <= s && e <= q) return T[idx];
		int m = s + e >> 1;
		return get(idx << 1, s, m, p, q) + get(idx << 1 | 1, m + 1, e, p, q);
	}
}seg;

int main() {
	scanf("%d%d", &N, &Q);
	for(int i = 1; i <= N; i++) {
		scanf("%d", &A[i]);
		seg.upd(1, 1, N, i, A[i]);
	}

	while(Q--) {
		int t, a, b; scanf("%d%d%d", &t, &a, &b);
		if(t == 1) seg.upd(1, 1, N, a, b);
		else printf("%lld\n", seg.get(1, 1, N, a, b).x);
	}
	return 0;
}