QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #725851 | #6435. Paimon Segment Tree | masttf | WA | 3ms | 3652kb | C++20 | 9.7kb | 2024-11-08 20:17:54 | 2024-11-08 20:17:55 |
Judging History
answer
#include<bits/stdc++.h>
// #define int long long
using namespace std;
#define dbg(x...) \
do { \
cout << #x << " -> "; \
err(x); \
} while (0)
void err() {
cout << endl << endl;
}
template<class T, class... Ts>
void err(T arg, Ts ... args) {
cout << fixed << setprecision(10) << arg << ' ';
err(args...);
}
template<const int T>
struct ModInt {
const static int mod = T;
int x;
ModInt(int x = 0) : x(x < 0 ? x % mod + mod : x % mod) {}
ModInt(long long x) : x(int(x % mod)) {}
int val() { return x; }
ModInt operator + (const ModInt &a) const {
int x0 = x + a.x;
return ModInt(x0 < mod ? x0 : x0 - mod);
}
ModInt operator - (const ModInt &a) const {
int x0 = x - a.x;
return ModInt(x0 < 0 ? x0 + mod : x0);
}
ModInt operator * (const ModInt &a) const {
return ModInt(1LL * x * a.x % mod);
}
ModInt operator / (const ModInt &a) const {
return *this * a.inv();
}
bool operator == (const ModInt &a) const {
return x == a.x;
}
bool operator != (const ModInt &a) const {
return x != a.x;
}
void operator += (const ModInt &a) {
x += a.x;
if (x >= mod) x -= mod;
}
void operator -= (const ModInt &a) {
x -= a.x;
if (x < 0) x += mod;
}
void operator *= (const ModInt &a) {
x = 1LL * x * a.x % mod;
}
void operator /= (const ModInt &a) {
*this = *this / a;
}
friend ModInt operator + (int y, const ModInt &a){
int x0 = y + a.x;
return ModInt(x0 < mod ? x0 : x0 - mod);
}
friend ModInt operator - (int y, const ModInt &a){
int x0 = y - a.x;
return ModInt(x0 < 0 ? x0 + mod : x0);
}
friend ModInt operator * (int y, const ModInt &a){
return ModInt(1LL * y * a.x % mod);
}
friend ModInt operator / (int y, const ModInt &a){
return ModInt(y) / a;
}
friend ostream &operator<<(ostream &os, const ModInt &a) {
return os << a.x;
}
friend istream &operator>>(istream &is, ModInt &t){
return is >> t.x;
}
ModInt pow(long long n) const {
ModInt res(1), mul(x);
while(n){
if (n & 1) res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
ModInt inv() const {
int a = x, b = mod, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
if (u < 0) u += mod;
return u;
}
};
constexpr int mod = 1e9 + 7;
using mint = ModInt<mod>;
template <const int M, class T>
struct Matrix{
T m[M][M];
int row, col;
Matrix(){
row = 0;
col = 0;
}
Matrix(int n){ //单位矩阵
row = col = n;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j)m[i][j] = 1;
else m[i][j] = 0;
}
}
}
Matrix(int r, int c){
row = r;
col = c;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
m[i][j] = 0;
}
}
}
Matrix(vector<vector<T>> a){
row = a.size();
col = a[0].size();
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
m[i][j] = a[i][j];
}
}
}
Matrix operator * (const Matrix &y) const {
Matrix res(row, y.col);
for(int i = 0; i < row; i++){
for(int j = 0; j < y.col; j++){
for(int k = 0; k < col; k++){
res.m[i][j] += m[i][k] * y.m[k][j];
}
}
}
return res;
}
Matrix operator + (const Matrix &y) const {
Matrix res(row, col);
for(int i = 0; i < row; i++){
for(int j = 0; j < y.col; j++){
res.m[i][j] = m[i][j] + y.m[i][j];
}
}
return res;
}
Matrix qmi (long long b){
Matrix res(row);
Matrix a = *this;
while(b){
if(b & 1) res = res * a;
b >>= 1;
a = a * a;
}
return res;
}
};
using matrix = Matrix<4, mint>;
template<class Info, class Tag>
struct LazySegmentTree{
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()){
init(n_, v_);
}
template<class T>
LazySegmentTree(vector<T> init_){ //注意下标从1开始也就是[0] 是空
init(init_);
}
void init(int n_, Info v_ = Info()){
init(vector(n_ + 1, v_));
}
template<class T>
void init(vector<T> init_){
n = init_.size() - 1;
info.assign(n * 4, Info());
tag.assign(n * 4, Tag());
auto bulid = [&](auto self, int l, int r, int p) -> void{
if(l == r){
info[p] = init_[l];
return ;
}
int mid = (l + r) >> 1;
self(self, l, mid, p << 1);
self(self, mid + 1, r, p << 1 | 1);
up(p);
};
bulid(bulid, 1, n, 1);
}
void cg(int p, const Tag &v){
info[p].apply(v);
tag[p].apply(v);
}
void up (int p){
info[p] = info[p << 1] + info[p << 1 | 1];
}
void down (int p){
cg(p << 1, tag[p]);
cg(p << 1 | 1, tag[p]);
tag[p] = Tag();
}
void update(int l, int r, int x, const Info &v, int p){
if(l == r){
info[p] = v;
return ;
}
down(p);
int mid = (l + r) >> 1;
if(x <= mid)update(l, mid, x, v, p << 1);
else update(mid + 1, r, x, v, p << 1 | 1);
up(p);
}
void update(int x, const Info &v){
update(1, n, x, v, 1);
}
Info rangeQuery(int l, int r, int x, int y, int p){
if(x <= l && r <= y)return info[p];
Info res = Info();
down(p);
int mid = (l + r) >> 1;
if(x <= mid)res = res + rangeQuery(l, mid, x, y, p << 1);
if(y > mid)res = res + rangeQuery(mid + 1, r, x, y, p << 1 | 1);
return res;
}
Info rangeQuery(int l, int r){
return rangeQuery(1, n, l, r, 1);
}
void rangeUpdate(int l, int r, int x, int y, const Tag &val, int p){
if(x <= l && r <= y){
cg(p, val);
return ;
}
down(p);
int mid = (l + r) >> 1;
if(x <= mid)rangeUpdate(l, mid, x, y, val, p << 1);
if(y > mid)rangeUpdate(mid + 1, r, x, y, val, p << 1 | 1);
up(p);
}
void rangeUpdate(int l, int r, const Tag &val){
rangeUpdate(1, n, l, r, val, 1);
}
template<class F>
int findFirst(int l, int r, int x, int y, int p, F &&check){
if(x <= l && r <= y){
if(!check(info[p]))return -1;
if(l == r)return l;
}
down(p);
int mid = (l + r) >> 1;
if(x <= mid){
int res = findFirst(l, mid, x, y, p << 1, check);
if(res != -1)return res;
}
if(y > mid)return findFirst(mid + 1, r, x, y, p << 1 | 1, check);
return -1;
}
template<class F>
int findFirst(int l, int r, F &&check){
return findFirst(1, n, l, r, 1, check);
}
template<class F>
int findLast(int l, int r, int x, int y, int p, F &&check){
if(x <= l && r <= y){
if(!check(info[p]))return -1;
if(l == r)return l;
}
down(p);
int mid = (l + r) >> 1;
if(y > mid){
int res = findLast(mid + 1, r, x, y, p << 1 | 1, check);
if(res != -1)return res;
}
if(x <= mid)return findLast(l, mid, x, y, p << 1, check);
return -1;
}
template<class F>
int findLast(int l, int r, F &&check){
return findLast(1, n, l, r, 1, check);
}
};
struct Tag{
matrix tag;
Tag() : tag(4) {}
Tag(matrix _tag) : tag(_tag){}
void apply(Tag t){
tag = tag * t.tag;
}
};
struct Info{
matrix val;
Info() : val(1, 4) {}
Info(matrix _val) : val(_val) {}
void apply(Tag t){
val = val * t.tag;
}
};
Info operator+ (const Info &a, const Info &b){
Info res = Info();
res.val = a.val + b.val;
return res;
}
void solve(){
int n, m, q; cin >> n >> m >> q;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
vector<array<int, 3>> b(m + 1);
vector<vector<array<int, 4>>> Q(m + 1);
for(int i = 1; i <= m; i++){
int l, r, x; cin >> l >> r >> x;
if(x < 0) x = x % mod + mod;
b[i] = {l, r, x};
}
vector<mint> ans(q + 1);
for(int i = 1; i <= q; i++){
int l, r, x, y; cin >> l >> r >> x >> y;
if(x != 0)Q[x - 1].push_back({l, r, -1, i});
Q[y].push_back({l, r, 1, i});
}
LazySegmentTree<Info, Tag> tr(n);
for(int i = 1; i <= n; i++){
matrix temp({{1, a[i], a[i] * a[i] % mod, a[i] * a[i] % mod}});
tr.update(i, {temp});
}
for(int i = 0; i <= m; i++){
if(i){
auto [l, r, x] = b[i];
matrix temp(4);
temp.m[2][3] = 1;
if(l > 1)tr.rangeUpdate(1, l - 1, {temp});
if(r < n)tr.rangeUpdate(r + 1, n, {temp});
temp.m[0][1] = x;
temp.m[0][2] = x * x % mod;
temp.m[0][3] = x * x % mod;
temp.m[1][2] = 2 * x % mod;
temp.m[1][3] = 2 * x % mod;
tr.rangeUpdate(l, r, {temp});
}
for(auto [l, r, f, id] : Q[i]){
if(f == 1)ans[id] += tr.rangeQuery(l, r).val.m[0][3];
else ans[id] -= tr.rangeQuery(l, r).val.m[0][3];
}
}
for(int i = 1; i <= q; i++){
cout << ans[i] << '\n';
}
return ;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3492kb
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: 1ms
memory: 3636kb
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: 3ms
memory: 3652kb
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:
910464947 744805405 516866029 633932682 841538379 531964975 793142832 235639442 39410711 445931864 239009809 248661783 555212419 428414542 14708306 64334299 366125337 13258986 522950590 200906453 730920893 748936780 887849685 630954363 669765326 454546983 483030185 392128579 235012432 388808992 4790...
result:
wrong answer 1st numbers differ - expected: '400489222', found: '910464947'