QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#256975 | #6435. Paimon Segment Tree | Satsuki | ML | 0ms | 0kb | C++17 | 3.3kb | 2023-11-18 23:22:52 | 2023-11-18 23:22:53 |
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 200010;
typedef long long ll;
const int mod = 1e9 + 7;
struct Matrix{
int n,m;
using point_t = ll;
vector<vector<point_t>> g;
Matrix(int n, int m) :n(n),m(m),g(n+1,vector<point_t>(m+1, 0)) {};
void clear(){
for(auto& row : g) {
std::fill(row.begin(), row.end(), 0);
}
for(int i = 1;i <= n;i++)g[i][i] = 1;
}
friend Matrix operator*(Matrix a,Matrix b){
Matrix ans(a.n, b.m);
for(int i=1;i<=a.n;i++)
for(int j=1;j<=b.m;j++){
for(int k=1;k<=a.m;k++)
(ans.g[i][j]+=a.g[i][k]*b.g[k][j]) %= mod;
}
return ans;
}
friend Matrix operator+(Matrix a,Matrix b){
Matrix ans(a.n, a.m);
for(int i=1;i<=a.n;i++)
for(int j=1;j<=a.m;j++){
(ans.g[i][j] = a.g[i][j] + b.g[i][j]) %= mod;
}
return ans;
}
};
#define ls (u << 1)
#define rs (u << 1 | 1)
#define A(u) (tr[u].A)
#define mk(u) (tr[u].mk)
struct node
{
int l, r;
Matrix A = Matrix(1, 4);
Matrix mk = Matrix(4, 4);
}tr[N << 2];
int a[N];
void pushup(int u)
{
A(u) = A(ls) + A(rs);
}
void build(int u,int l,int r)
{
if(l == r)
{
tr[u] = {l,r};
A(u).g[1][1] = 1;
A(u).g[1][2] = a[l];
A(u).g[1][3] = a[l] * a[l] % mod;
A(u).g[1][4] = a[l] * a[l] % mod;
mk(u).clear();
}
else
{
int mid = l + r >> 1;
tr[u] = {l,r};
mk(u).clear();
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
}
void pushdown(int u)
{
A(ls) = A(ls) * mk(u);
mk(ls) = mk(ls) * mk(u);
A(rs) = A(rs) * mk(u);
mk(rs) = mk(rs) * mk(u);
mk(u).clear();
}
Matrix B = Matrix(4,4);
void upd(int u,int l,int r,int k)
{
if(tr[u].l >= l && tr[u].r <= r)
{
B.g[1][1] = 1;
B.g[1][2] = k;
B.g[2][2] = 1;
B.g[1][3] = k * k % mod;
B.g[1][4] = k * k % mod;
B.g[2][3] = 2 * k % mod;
B.g[2][4] = 2 * k % mod;
B.g[3][3] = 1;
B.g[3][4] = 1;
B.g[4][4] = 1;
A(u) = A(u) * B;
mk(u) = mk(u) * B;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
if(l <= mid)upd(ls, l, r, k);
if(r > mid)upd(rs, l ,r ,k);
pushup(u);
}
}
int que(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return A(u).g[1][4];
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
pushdown(u);
if(l <= mid)res += que(ls, l, r);
if(r > mid)res = (res + que(rs, l, r)) % mod;
return res;
}
}
struct qu
{
int l,r,k,id;
}modi[N];
int ans[N];
vector<qu> q[N];
void solve()
{
int n,m,k;cin >> n >> m >> k;
for(int i = 1;i <= n;i++)cin >> a[i];
build(1,1,n);
for(int i = 1;i <= m;i++)
{
cin >> modi[i].l >> modi[i].r >> modi[i].k;
}
for(int i = 1;i <= k;i++)
{
int l,r;cin >> l >> r;
int x,y;cin >> x >> y;
if(x)
q[x - 1].push_back({l, r, -1, i});
q[y].push_back({l, r, 1, i});
}
for(int i = 0;i <= m;i++)
{
if(i)
{
upd(1, modi[i].l, modi[i].r, modi[i].k);
if(modi[i].l > 1)
upd(1, 1, modi[i].l - 1, 0);
if(modi[i].r < n)
upd(1, modi[i].r + 1, n, 0);
}
for(auto t : q[i])
{
// cout << t.id <<" " << que(1,t.l,t.r) << endl;
(ans[t.id] += t.k * que(1, t.l, t.r)) %= mod;
}
}
for(int i = 1;i <= k;i++)
{
cout << (ans[i] + mod)% mod << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);
solve();
}
详细
Test #1:
score: 0
Memory Limit Exceeded
input:
3 1 1 8 1 6 2 3 2 2 2 0 0
output:
1