冷滟泽的个人博客A - Sasha and Array: CodeForces - 718C
题意
维护一个序列
- 区间加上一个正整数
- 查询
\sum_{i=l}^{r} f(a_i) ，f(i) 表示斐波那契数列的第i 项
思路
线段树维护矩阵
代码
#pragma GCC optimize(3, "Ofast", "inline")
#include <cstdio>
#include <cstring>
#include <cctype>
#include <tr1/unordered_map>
using namespace std;
typedef long long ll;
const int MAXN=110000;
const int MAXB=100;
const int MOD=1E9+7;
struct Matrix
{
int n, m, a[5][5];
Matrix operator + (const Matrix& b)
{
Matrix c(n, m);
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
c.a[i][j]=(a[i][j]+b.a[i][j])%MOD;
return c;
}
Matrix operator * (const Matrix& b)
{
Matrix c(n, b.m);
for (int i=0; i<n; i++)
for (int j=0; j<b.m; j++)
for (int k=0; k<m; k++)
c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*b.a[k][j])%MOD;
return c;
}
bool isid()
{
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
if (i==j&&a[i][j]==0||i!=j&&a[i][j]!=0) return 0;
return 1;
}
Matrix(int r=0, int c=0, bool id=0)
{
n=r, m=c;
memset(a, 0, sizeof a);
if (id) for (int i=0; i<r; i++) a[i][i]=1;
}
} b[MAXB];
void prework()
{
b[0]=Matrix(2, 2);
b[0].a[0][0]=1; b[0].a[0][1]=1; b[0].a[1][0]=1;
for (int i=1; i<MAXB; i++)
b[i]=b[i-1]*b[i-1];
}
Matrix qpow(ll k)
{
Matrix s(2, 2, 1);
for (int t=0; k; t++, k>>=1)
if (k&1) s=s*b[t];
return s;
}
struct SegmentTree
{
struct Node
{
Matrix val, mul;
} tr[4*MAXN];
#define lc (o<<1)
#define rc (o<<1|1)
inline void pushup(int o)
{
tr[o].val=tr[lc].val+tr[rc].val;
}
inline void mul(int o, const Matrix& k)
{
tr[o].val=tr[o].val*k;
tr[o].mul=tr[o].mul*k;
}
inline void pushdown(int o)
{
if (!tr[o].mul.isid())
{
mul(lc, tr[o].mul);
mul(rc, tr[o].mul);
tr[o].mul=Matrix(2, 2, 1);
}
}
void build(int o, int l, int r, int* a)
{
tr[o].mul=Matrix(2, 2, 1);
if (l==r) { tr[o].val=qpow(a[l]-1); return; }
int mid=l+r>>1;
build(lc, l, mid, a);
build(rc, mid+1, r, a);
pushup(o);
}
void update(int o, int l, int r, int ul, int ur, const Matrix& k)
{
if (l>ur||r<ul) return;
if (ul<=l&&r<=ur) { mul(o, k); return; }
pushdown(o); int mid=l+r>>1;
update(lc, l, mid, ul, ur, k);
update(rc, mid+1, r, ul, ur, k);
pushup(o);
}
int query(int o, int l, int r, int ql, int qr)
{
if (l>qr||r<ql) return 0;
if (ql<=l&&r<=qr) return tr[o].val.a[0][0];
pushdown(o); int mid=l+r>>1;
return (query(lc, l, mid, ql, qr)
+query(rc, mid+1, r, ql, qr))%MOD;
}
#undef lc
#undef rc
} st;
int a[MAXN];
inline int read()
{
int x=0; char ch=0;
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
return x;
}
inline void write(int x)
{
if (x>9) write(x/10);
putchar(x%10+'0');
}
int main()
{
// freopen("A.in", "r", stdin);
// freopen("A.out", "w", stdout);
int n=read(), m=read();
for (int i=1; i<=n; i++) a[i]=read();
prework();
st.build(1, 1, n, a);
while (m--)
{
int op=read(), l=read(), r=read(), x;
if (op==1) x=read(), st.update(1, 1, n, l, r, qpow(x));
else write(st.query(1, 1, n, l, r)), putchar('\n');
}
return 0;
}B - 回转寿司: HYSBZ - 4627
题意
在一个序列中选择一段区间，使这段区间中元素之和在
思路
枚举右端点，用平衡树维护以它右端点的区间和，右端点向右移动相当于整体加操作，统计答案即统计有多少值在
代码
#include <cstdio>
#include <cstdlib>
typedef long long ll;
const int MAXN=110000;
struct Treap
{
struct Node
{
int ls, rs, wgt, siz;
ll val, add;
} tr[MAXN];
int cnt, root;
inline int newNode(int k)
{
int x=++cnt;
tr[x].ls=tr[x].rs=0; tr[x].wgt=rand();
tr[x].siz=1; tr[x].val=k; tr[x].add=0;
return x;
}
inline void pushup(int x)
{
tr[x].siz=1;
if (tr[x].ls) tr[x].siz+=tr[tr[x].ls].siz;
if (tr[x].rs) tr[x].siz+=tr[tr[x].rs].siz;
}
inline void add(int x, int k)
{
if (x) tr[x].val+=k, tr[x].add+=k;
}
inline void pushdown(int x)
{
if (x&&tr[x].add)
{
if (tr[x].ls) add(tr[x].ls, tr[x].add);
if (tr[x].rs) add(tr[x].rs, tr[x].add);
tr[x].add=0;
}
}
void split(int o, int& x, int& y, int k)
{
pushdown(o);
if (!o) x=y=0;
else if (tr[o].val<k)
x=o, split(tr[o].rs, tr[x].rs, y, k), pushup(x);
else y=o, split(tr[o].ls, x, tr[y].ls, k), pushup(y);
}
void merge(int x, int y, int& o)
{
pushdown(x); pushdown(y);
if (!x||!y) o=x+y;
else if (tr[x].wgt<tr[y].wgt)
o=x, merge(tr[x].rs, y, tr[o].rs), pushup(o);
else o=y, merge(x, tr[y].ls, tr[o].ls), pushup(o);
}
void insert(int k)
{
int x, y, z, w=newNode(k);
split(root, x, y, k);
merge(x, w, z);
merge(z, y, root);
}
int query(int l, int r)
{
int x, y, z, w;
split(root, x, y, l);
split(y, z, w, r+1);
int res=tr[z].siz;
merge(x, z, y);
merge(y, w, root);
return res;
}
} treap;
int main()
{
// freopen("B.in", "r", stdin);
// freopen("B.out", "w", stdout);
int n, l, r;
scanf("%d%d%d", &n, &l, &r);
ll ans=0;
for (int i=1; i<=n; i++)
{
int x; scanf("%d", &x);
treap.add(treap.root, x);
treap.insert(x);
ans+=treap.query(l, r);
}
printf("%lld\n", ans);
return 0;
}C - 一次元リバーシ / 1D Reversi: AtCoder - 2146
题意
有一排白色或黑色的石头。每次操作你可以在左右两端加一颗这样的石头，并把它与离他最近的同色石头之间的石头都改为它的颜色。问最少的操作次数。
思路
观察样例不难发现，最少的操作次数就是前后两个颜色不同的个数。直接统计答案即可。
代码
#include <cstdio>
const int MAXN=110000;
char s[MAXN];
int main()
{
// freopen("C.in", "r", stdin);
// freopen("C.out", "w", stdout);
int ans=0;
scanf("%s", s);
for (int i=1; s[i]; i++)
if (s[i]!=s[i-1]) ans++;
printf("%d\n", ans);
return 0;
}D - 高橋君と見えざる手 / An Invisible Hand [AtCoder - 2147]
题意
有一些城镇，从
思路
无论
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=110000;
const int INF=0X3F3F3F3F;
int a[MAXN];
int main()
{
// freopen("D.in", "r", stdin);
// freopen("D.out", "w", stdout);
int n, t;
scanf("%d%d", &n, &t);
for (int i=1; i<=n; i++) scanf("%d", &a[i]);
int mx=0, ans=0;
for (int i=1, mi=INF; i<=n; i++)
{
mi=min(mi, a[i]);
if (a[i]-mi>mx) mx=a[i]-mi, ans=0;
if (a[i]-mi==mx) ans++;
}
printf("%d\n", ans);
return 0;
}E - 木と整数 / Integers on a Tree: AtCoder - 2148
题意
有一个
思路
按点权的奇偶性将点分为黑点和白点。一遍 DFS 对这棵树进行黑白染色，若矛盾则无解。再次 DFS ，对每个点维护一个区间集合表示它的取值范围，若一个点的儿子的集合为
代码
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN=110000;
const int INF=1E7;
vector<int> g[MAXN];
int w[MAXN], l[MAXN], r[MAXN];
bool c[MAXN];
bool dfs1(int u, int f, bool t)
{
c[u]=t;
if (~w[u]&&w[u]%2!=t) return 0;
for (int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if (v!=f&&!dfs1(v, u, t^1)) return 0;
}
return 1;
}
int dfs2(int u, int f)
{
if (~w[u]) l[u]=r[u]=w[u];
for (int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if (v==f) continue;
if (!dfs2(v, u)) return 0;
l[u]=max(l[u], l[v]-1);
r[u]=min(r[u], r[v]+1);
}
return l[u]<=r[u];
}
void dfs3(int u, int f, int k)
{
w[u]=k;
for (int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if (v==f) continue;
if (l[v]<=k-1&&k-1<=r[v]) dfs3(v, u, k-1);
else dfs3(v, u, k+1);
}
}
int main()
{
// freopen("E.in", "r", stdin);
// freopen("E.out", "w", stdout);
int n, k;
scanf("%d", &n);
for (int i=1; i<n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
scanf("%d", &k);
memset(w, -1, sizeof w);
for (int i=1; i<=k; i++)
{
int v, p;
scanf("%d%d", &v, &p);
w[v]=p;
}
for (int i=1; i<=n; i++)
if (~w[i])
{
if (!dfs1(i, 0, w[i]%2))
{ puts("No"); return 0; }
break;
}
for (int i=1; i<=n; i++) l[i]=-INF, r[i]=INF;
if (!dfs2(1, 0)) { puts("No"); return 0; }
puts("Yes");
dfs3(1, 0, l[1]);
for (int i=1; i<=n; i++) printf("%d\n", w[i]);
return 0;
}