A.环鸽的CHONG
对于a[i] = x而言，最大的区间[l, r]只包含一个x，那么这个区间[l, r]是一个好区间,依次递归判断是否[l, i - 1]和[i + 1, r]这两个区间同时满足是好区间，预处理每一个数前一次出现的位置和后一次出现的位置，然后递归处理即可。
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_map>
typedef long long LL;
using namespace std;
int n, a[200005], l[200005], r[200005];
unordered_map<int, int> mp;
int dfs(int L, int R){
if(R - L <= 0) return true;
int x = L, y = R, mid = -1;
while(x <= y){
if(l[x] < L && R < r[x]) {mid = x; break;}
if(l[y] < L && R < r[y]) {mid = y; break;}
x++, y--;
}
if(mid == -1) return false;
return dfs(L, mid - 1) && dfs(mid + 1, R);
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++){
if(!mp[a[i]]) l[i] = 0;
else l[i] = mp[a[i]];
mp[a[i]] = i;
}
mp.clear();
for (int i = n; i >= 1; i--){
if(!mp[a[i]]) r[i] = n + 1;
else r[i] = mp[a[i]];
mp[a[i]] = i;
}
if(dfs(1, n)) printf("chong\n");
else printf("fuchong\n");
return 0;
}
/**/ B. 环鸽的数列列
对于每一个区间添加操作，都是从F1开始添加。
构造矩阵:
所以有
，特别的有
,那么我们维护区间[L, R]的时候，如果知道区间左端点L的矩阵为A，那么区间总和可以表示为
，所以，我们可以先预处理出
的前缀和用
来维护区间左端点的值。对于区间左端点L的矩阵初始化为
，然后用线段树维护区间和即可
，特别的有,那么我们维护区间[L, R]的时候，如果知道区间左端点L的矩阵为A，那么区间总和可以表示为，所以，我们可以先预处理出的前缀和用来维护区间左端点的值。对于区间左端点L的矩阵初始化为，然后用线段树维护区间和即可 /**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
const long long mod = 998244353;
int n, m, a[100005];
struct M
{
LL m[2][2];
friend M operator +(M a, M b){
M c;
memset(c.m, 0, sizeof(c.m));
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
c.m[i][j] = (a.m[i][j] + b.m[i][j]) % mod;
}
}
return c;
}
friend M operator -(M a, M b){
M c;
memset(c.m, 0, sizeof(c.m));
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
c.m[i][j] = (a.m[i][j] - b.m[i][j] + mod) % mod;
}
}
return c;
}
friend M operator *(M a, M b){
M c;
memset(c.m, 0, sizeof(c.m));
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
for (int k = 0; k < 2; k++){
c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % mod) % mod;
}
}
}
return c;
}
}tr[100005 << 2], lzy[100005 << 2], p[100005], sum[100005];
void up(int rt){
tr[rt] = tr[rt << 1] + tr[rt << 1 | 1];
}
void down(int rt, int l, int r){
int mid = (l + r) >> 1;
lzy[rt << 1] = lzy[rt << 1] + lzy[rt];
lzy[rt << 1 | 1] = lzy[rt << 1 | 1] + (lzy[rt] * p[mid + 2 - l]);
tr[rt << 1] = tr[rt << 1] + (sum[mid - l + 1] * lzy[rt]);
tr[rt << 1 | 1] = tr[rt << 1 | 1] + ((sum[r - l + 1] - sum[mid - l + 1]) * lzy[rt]);
memset(lzy[rt].m, 0, sizeof(lzy[rt].m));
}
void build(int rt, int l, int r){
lzy[rt].m[0][0] = lzy[rt].m[0][1] = lzy[rt].m[1][0] = lzy[rt].m[1][1] = 0;
tr[rt] = lzy[rt];
if(l == r){
tr[rt].m[0][0] = a[l];
return ;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
up(rt);
}
void update(int rt, int l, int r, int L, int R){
if(L <= l && r <= R){
lzy[rt] = lzy[rt] + p[l - L + 1];
tr[rt] = tr[rt] + (sum[r - L + 1] - sum[l - L]);
return ;
}
down(rt, l, r);
int mid = (l + r) >> 1;
if(mid >= L) update(rt << 1, l, mid, L, R);
if(mid < R) update(rt << 1 | 1, mid + 1, r, L, R);
up(rt);
}
LL query(int rt, int l, int r, int L, int R){
if(L <= l && r <= R) return tr[rt].m[0][0];
down(rt, l, r);
int mid = (l + r) >> 1;
LL ans = 0;
if(mid >= L) ans = (ans + query(rt << 1, l, mid, L, R)) % mod;
if(mid < R) ans = (ans + query(rt << 1 | 1, mid + 1, r, L, R)) % mod;
return (ans % mod + mod) % mod;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
p[1].m[0][0] = p[1].m[1][1] = 1;
p[1].m[0][1] = p[1].m[1][0] = 0;
sum[1] = p[1];
M b;
b.m[0][0] = 3, b.m[0][1] = 2, b.m[1][0] = 1, b.m[1][1] = 0;
for (int i = 2; i <= 100000; i++) p[i] = p[i - 1] * b, sum[i] = sum[i - 1] + p[i];
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
for (int i = 1, op, l, r; i <= m; i++){
scanf("%d %d %d", &op, &l, &r);
if(l > r) swap(l, r);
if(op == 1){
update(1, 1, n, l, r);
}else{
printf("%lld\n", query(1, 1, n, l, r));
}
}
return 0;
}
/*
4 10
1 2 3 4
1 1 4
2 4 4
2 3 3
1 2 4
2 1 1
2 2 2
2 3 3
2 4 4
2 3 4
*/ C.环鸽不会X点
1. 对于2*k次操作最少造成(1 + 2) * k点伤害
2. 判断n和k的奇偶性不同(偶*偶为偶，奇*奇为奇)
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int t, n, k;
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &t);
while(t--){
scanf("%d %d", &n, &k);
if(n < 3LL * k) printf("No\n");
else{
if(n % 2 != k % 2) printf("No\n");
else printf("Yes\n");
}
}
return 0;
}
/**/ D. 小C的棋王之路
线段树区间维护乘，加，赋值模板题
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
const int mx = 200000;
int n, m, a[200005];
LL mod, tr[200005 << 2], lzy_add[200005 << 2], lzy_mu[200005 << 2];
void up(int rt){
tr[rt] = (tr[rt << 1] + tr[rt << 1 | 1]) % mod;
}
void build(int rt, int l, int r){
lzy_mu[rt] = 1;
if(l == r){
tr[rt] = a[l];
return ;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
up(rt);
}
void update(int rt, int l, int r, int L, int R, int k, int x){
// printf("%d %d\n", l, r);
if(L == l && r == R){
tr[rt] = (tr[rt] * x % mod + (LL)k * (r - l + 1) % mod) % mod;
lzy_mu[rt] = lzy_mu[rt] * x % mod, lzy_add[rt] = (lzy_add[rt] * x % mod + k) % mod;
return ;
}
int mid = (l + r) >> 1;
if(lzy_mu[rt] != 1 || lzy_add[rt]){
update(rt << 1, l, mid, l, mid, lzy_add[rt], lzy_mu[rt]);
update(rt << 1 | 1, mid + 1, r, mid + 1, r, lzy_add[rt], lzy_mu[rt]);
lzy_add[rt] = 0, lzy_mu[rt] = 1;
}
if(mid >= R) update(rt << 1, l, mid, L, R, k, x);
else if(mid < L) update(rt << 1 | 1, mid + 1, r, L, R, k, x);
else update(rt << 1, l, mid, L, mid, k, x), update(rt << 1 | 1, mid + 1, r, mid + 1, R, k, x);
up(rt);
}
LL query(int rt, int l, int r, int L, int R){
if(L == l && r == R) return tr[rt];
int mid = (l + r) >> 1;
if(lzy_mu[rt] != 1 || lzy_add[rt]){
update(rt << 1, l, mid, l, mid, lzy_add[rt], lzy_mu[rt]);
update(rt << 1 | 1, mid + 1, r, mid + 1, r, lzy_add[rt], lzy_mu[rt]);
lzy_add[rt] = 0, lzy_mu[rt] = 1;
}
if(mid >= R) return query(rt << 1, l, mid, L, R);
else if(mid < L) return query(rt << 1 | 1, mid + 1, r, L, R);
else return (query(rt << 1, l, mid, L, mid) + query(rt << 1 | 1, mid + 1, r, mid + 1, R)) % mod;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d %d %lld", &n, &m, &mod);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, mx);
for (int i = 1, op, l, r, k, x; i <= m; i++){
scanf("%d", &op);
if(op == 1){
scanf("%d %d %d", &l, &r, &k);
update(1, 1, mx, l, r, k, 1);
}else if(op == 2){
scanf("%d %d %d", &l, &r, &k);
update(1, 1, mx, l, r, 0, k);
}else if(op == 3){
scanf("%d %d %d", &l, &r, &k);
update(1, 1, mx, l, r, k, 0);
}else if(op == 4){
scanf("%d", &x);
n++;
update(1, 1, mx, n, n, x, 0);
}else{
scanf("%d %d", &l, &r);
if(l > r) swap(l, r);
printf("%lld\n", query(1, 1, mx, l, r));
}
}
return 0;
}
/**/
或者直接套珂朵莉树板子
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n, m;
LL mod;
struct node
{
int l, r;
mutable LL val;
node(int l, int r = -1, LL val = 0) : l(l), r(r), val(val) {}
bool operator <(const node &rhs)const{
return l < rhs.l;
}
};
set<node> s;
auto split(int x){
auto it = s.lower_bound(x);
if(it != s.end() && it->l == x) return it;
--it;
int l = it->l, r = it->r;
LL val = it->val;
s.erase(it);
s.insert(node(l, x - 1, val));
return s.insert(node(x, r, val)).first;
}
void add(int l, int r, int x){
auto itr = split(r + 1), itl = split(l);
for (; itl != itr; itl++) itl->val = (itl->val + x) % mod;
}
void mul(int l, int r, int x){
auto itr = split(r + 1), itl = split(l);
for (; itl != itr; itl++) itl->val = itl->val * x % mod;
}
void assign(int l, int r, int x){
auto itr = split(r + 1), itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, x));
}
LL query(int l, int r){
LL ans = 0;
auto itr = split(r + 1), itl = split(l);
for (; itl != itr; itl++) ans = (ans + itl->val * (itl->r - itl->l + 1) % mod) % mod;
return ans;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d %d %lld", &n, &m, &mod);
for (int i = 1, x; i <= n; i++){
scanf("%d", &x);
s.insert(node(i, i, x));
}
++n;
s.insert(node(n, n, 0));
for (int i = 1, op, l, r, k, x; i <= m; i++){
scanf("%d", &op);
if(op <= 3){
scanf("%d %d %d", &l, &r, &k);
if(op == 1) add(l, r, k);
else if(op == 2) mul(l, r, k);
else assign(l, r, k);
}else if(op == 4){
scanf("%d", &x);
auto it = s.lower_bound(node(n));
s.erase(it);
s.insert(node(n, n, x));
++n;
s.insert(node(n, n, 0));
}else{
scanf("%d %d", &l, &r);
printf("%lld\n", query(l, r));
}
}
return 0;
}
/**/ E. 兰德索尔的瞭望塔
将一个点连接原点
首先将l[i]根据斜率从小到大排序
然后问题即转化为求r[i]的最长严格上升子序列(这里所谓的上升具体看下图)
对于当前线i，用dp[i] = max{dp[j]} + 1, (1 <= j< i且满足j线在i线的逆时针方向)
判断一条线在另一条线的方向时，用几何里的叉积即可(
表示j线在i线逆时针方向, = 0表示同线，< 0 表示顺时针方向)
表示j线在i线逆时针方向, = 0表示同线，< 0 表示顺时针方向) 最后注意l[i]斜率相同情况即可
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n, x, ans, dp[100005];
struct node
{
LL x, y;
friend LL operator * (node a, node b){
return a.x * b.y - a.y * b.x;
}
friend node operator - (node a, node b){
return node{a.x - b.x, a.y - b.y};
}
bool operator <(const node &rhs)const{
return x * rhs.y - y * rhs.x > 0LL;
}
}b[100005], a[100005];
int check(node a, node b){
return a * b > 0LL;
}
int solve(node a){
int l = 1, r = ans, res = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(check(a - node{x, 0}, b[mid])) res = mid, l = mid + 1;
else r = mid - 1;
}
return res;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
while(scanf("%d %d", &n, &x) == 2){
for (int i = 1; i <= n; i++) scanf("%lld %lld", &a[i].x, &a[i].y);
sort(a + 1, a + 1 + n);
ans = 0;
for (int i = 1, j; i <= n; i = j){
j = i + 1;
while(a[j] * a[i] == 0 && j <= n) j++;
int p = i;
for (int k = i + 1; k < j; k++) if(check(a[p] - node{x, 0}, a[k] - node{x, 0})) p = k;
b[dp[p] = solve(a[p]) + 1] = a[p] - node{x, 0};
ans = max(ans, dp[p]);
}
printf("%d\n", ans);
}
return 0;
}
/**/ 
京公网安备 11010502036488号