QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#256975#6435. Paimon Segment TreeSatsukiML 0ms0kbC++173.3kb2023-11-18 23:22:522023-11-18 23:22:53

Judging History

你现在查看的是最新测评结果

  • [2023-11-18 23:22:53]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2023-11-18 23:22:52]
  • 提交

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

result: