QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#250634 | #6435. Paimon Segment Tree | hhoppitree# | WA | 5ms | 22000kb | C++14 | 3.9kb | 2023-11-13 14:35:38 | 2023-11-13 14:35:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 50005, P = 1e9 + 7;
int a[N], _l[N], _r[N], _v[N], A[N];
vector< pair<int, pair<int, int> > > qr[N];
struct mat
{
int o[4][4];
mat(int a = 1, int b = 0, int c = 0, int d = 0, int e = 0, int f = 1, int g = 0, int h = 0, int i = 0, int j = 0, int k = 1, int l = 0, int m = 0, int n = 0, int O = 0, int p = 1)
{
o[0][0] = a, o[0][1] = b, o[0][2] = c, o[0][3] = d;
o[1][0] = e, o[1][1] = f, o[1][2] = g, o[1][3] = h;
o[2][0] = i, o[2][1] = j, o[2][2] = k, o[2][3] = l;
o[3][0] = m, o[3][1] = n, o[3][2] = O, o[3][3] = p;
return;
}
mat operator + (mat y)
{
mat res;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
((res.o[i][j] = o[i][j] + y.o[i][j]) >= P) && (res.o[i][j] -= P);
}
}
return res;
}
mat operator * (mat y)
{
mat res(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
for (int i = 0; i < 4; ++i) {
for (int k = 0; k < 4; ++k) {
for (int j = 0; j < 4; ++j) {
res.o[i][j] = (res.o[i][j] + 1ll * o[i][k] * y.o[k][j]) % P;
}
}
}
return res;
}
} p[1 << 17], q[1 << 17];
void build(int k, int l, int r)
{
if (l == r) {
return;
}
int mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
p[k] = p[k << 1] + p[k << 1 | 1];
return;
}
void modify(int k, int l, int r, int x, int y, mat o)
{
if (l > y || r < x) {
return;
}
if (l >= x && r <= y) {
p[k] = p[k] * o;
q[k] = q[k] * o;
return;
}
p[k << 1] = p[k << 1] * q[k];
q[k << 1] = q[k << 1] * q[k];
p[k << 1 | 1] = p[k << 1 | 1] * q[k];
q[k << 1 | 1] = q[k << 1 | 1] * q[k];
q[k] = mat();
int mid = (l + r) >> 1;
modify(k << 1, l, mid, x, y, o);
modify(k << 1 | 1, mid + 1, r, x, y, o);
p[k] = p[k << 1] + p[k << 1 | 1];
return;
}
mat query(int k, int l, int r, int x, int y)
{
if (l > y || r < x) {
return mat(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
}
if (l >= x && r <= y) {
return p[k];
}
p[k << 1] = p[k << 1] * q[k];
q[k << 1] = q[k << 1] * q[k];
p[k << 1 | 1] = p[k << 1 | 1] * q[k];
q[k << 1 | 1] = q[k << 1 | 1] * q[k];
q[k] = mat();
int mid = (l + r) >> 1;
return query(k << 1, l, mid, x, y) + query(k << 1 | 1, mid + 1, r, x, y);
}
signed main()
{
int n, m, q;
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &_l[i], &_r[i], &_v[i]);
}
for (int i = 1; i <= q; ++i) {
int l, r, x, y;
scanf("%d%d%d%d", &l, &r, &x, &y);
if (x) {
qr[x - 1].push_back(make_pair(-i, make_pair(l, r)));
}
qr[y].push_back(make_pair(i, make_pair(l, r)));
}
build(1, 1, n);
for (int i = 0; i <= m; ++i) {
if (i) {
int v = _v[i];
modify(1, 1, n, _l[i], _r[i], mat(1, v, 1ll * v * v % P, 0, 0, 1, (v + v) % P, 0, 0, 0, 1, 0, 0, 0, 0, 1));
} else {
for (int j = 1; j <= n; ++j) {
int v = a[j];
modify(1, 1, n, j, j, mat(1, v, 1ll * v * v % P, 0, 0, 1, (v + v) % P, 0, 0, 0, 1, 0, 0, 0, 0, 1));
}
}
modify(1, 1, n, 1, n, mat(1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1));
for (auto t : qr[i]) {
A[abs(t.first)] += (t.first > 0 ? 1 : -1) * (query(1, 1, n, t.second.first, t.second.second).o[0][3]);
}
}
for (int i = 1; i <= q; ++i) {
printf("%d\n", (A[i] % P + P) % P);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 21196kb
input:
3 1 1 8 1 6 2 3 2 2 2 0 0
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 22000kb
input:
4 3 3 2 3 2 2 1 1 6 1 3 3 1 3 6 2 2 2 3 1 4 1 3 4 4 2 3
output:
180 825 8
result:
ok 3 number(s): "180 825 8"
Test #3:
score: -100
Wrong Answer
time: 5ms
memory: 21192kb
input:
100 107 180 -280960553 266308104 -997644864 856103777 592874377 674379235 -946339772 641750362 642418716 -360811715 -555543246 206614021 358239245 349842656 983198973 807518446 -66612455 -980932737 109826132 -109676067 51226145 452115561 -42729559 -950621304 -87009773 714026474 375317493 693260053 -...
output:
400489222 480617351 236141257 549951029 446689548 14056028 142229431 602373057 219686346 66225912 247029353 353738418 529135498 586096834 201809860 674078444 746060191 171471121 902340538 657196163 156519099 606551808 360903956 632566225 767571915 922826851 163759234 141144218 579174939 276557168 34...
result:
wrong answer 3rd numbers differ - expected: '531108525', found: '236141257'