[SDOI2019] 快速查询

首先,这是一道省选可以切的题(虽然我其实一开始并不会)。

分析6个操作,不难发现其实所有的操作要么是单点修改/查询,要么是整个序列的修改/查询。而众所周知,只对整个序列进行操作有些优美的性质。

首先我们维护3个标记,\(add\),\(mul\),\(sum\),分别是加法标记,乘法标记,以及整个序列的和。类似于线段树的思想。

先考虑对整个序列的操作:

对于操作2,实际上就是把 \(add\) 标记加上 \(val\),然后\(sum\) 加上 \(val \times n\),根据加法交换律显然成立。

对于操作3,\(add\)标记,\(mul\)标记,\(sum\)标记都\(\times val\),根据分配律,这也是成立的。

对于操作4,赋值的话标记都没用了,直接变成初值:\(add=0,mul=1\),然后\(sum=val \times n\)。

对于操作6,答案显然就是\(sum\)。

现在考虑单点操作,对于每个点\(x\),实际这个点的权值并不是\(a_x\),而是\(mul * a_x + add\),那修改的时候直接操作显然会导致权值并不是\(val\),而是\(mul \times val + add\),所以不妨设我们应该改为\(val'\),为了满足要求,有\(val=mul \times val' + add\),解得\(val' = \frac{val-add}{mul}\),这样就可以修改了。

查询的时候其实会出现问题,因为区间操作可能覆盖单点操作,反之亦然。为解决这个问题,不妨维护一个时间戳,记录一下这个点上次单点修改的时间,以及上次区间修改的时间,谁在后面那谁的值就是答案了。

直接用数组可以获得50分的暴力分,如果想切掉还要继续优化下。

注意到输入格式又臭又长,但是其实本质上执行的操作只有\(q\)个,不过是重复若干次,所以不妨用一个哈希表,把可能涉及到的点都存下来,每次单点修改/查询的时候直接在哈希表里进行查询,这样复杂度就和\(n\)没有关系了,只和\(q\)有关系了,那么就可以切掉这道题了。

吐槽:Luogu评测机太慢了,同样的代码在loj能过而在Luogu就会TLE。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<iostream>
#include<queue>
#include<cctype>
#include<ctime>
#include<unordered_map>
using namespace std;

#define A(x) cout << #x << " " << x << endl;
#define AA(x,y) cout << #x << " " << x << " " << #y << " " << y << endl;
#define AAA(x,y,z) cout << #x << " " << x << " " << #y << " " << y  << " " << #z << " " << z << endl;
#define B cout << "Break" << endl;
#define ll long long
#define inf 1000000000

ll read()
{
	char c = getchar();
	ll x = 0,f = 1;
	while(!isdigit(c))
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(isdigit(c))
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return f * x;
}
#define mod 10000019
ll add,mul = 1,sum,n,q,ans;
struct opt
{
	ll tim,x,val;
}lst;
vector<opt>h[mod];
ll quick_pow(ll a,ll b)
{
	ll ret = 1;
	while(b)
	{
		if(b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}
ll query(ll x)
{
	ll pos = x % mod;
	for(int i = 0;i < h[pos].size();++i)
	{
		if(h[pos][i].x != x) continue;
		if(h[pos][i].tim < lst.tim) return (mul * lst.val + add + mod) % mod;
		else return (mul * h[pos][i].val + add + mod) % mod;
	}
	return (mul * lst.val + add + mod) % mod;
}
struct Query
{
	ll op,x,val;
}qu[100010];
void push(ll x,ll val,ll tim)
{
	ll pos = x % mod;
	for(int i = 0;i < h[pos].size();++i)
	{
		if(h[pos][i].x == x)
		{
			h[pos][i].val = val,h[pos][i].tim = tim;
			return;
		}
	}
	h[pos].push_back({tim,x,val});
}
void calc(ll num,ll tim)
{
	ll op = qu[num].op,x = qu[num].x,val = qu[num].val;
	if(op == 1)
	{
		ll tp = query(x);
		sum = (sum + val - tp + mod) % mod;
		val = (val - add + mod) % mod * quick_pow(mul,mod - 2) % mod;
		push(x,val,tim);
	}
	else if(op == 2)
	{
		add = ((add + val) % mod + mod) % mod;
		sum = ((sum + val * n) % mod + mod) % mod;
	}
	else if(op == 3)
	{
		add = (add * val % mod + mod) % mod;
		mul = (mul * val % mod + mod) % mod;
		sum = (sum * val % mod + mod) % mod;
	}
	else if(op == 4)
	{
		lst.tim = tim,lst.val = val;
		sum = val * n % mod;
		add = 0,mul = 1;
	}
	else if(op == 5)
		ans = (ans + query(qu[num].x) + mod) % mod;
	else
		ans = (ans + sum % mod + mod) % mod;
	return;
}
ll a[100010],b[100010];
int main()
{
	n = read(),q = read();
	for(ll i = 1;i <= q;++i)
	{
		qu[i].op = read();
		if(qu[i].op == 1) qu[i].x = read(),qu[i].val = read();
		else if(qu[i].op <= 4) qu[i].val = read();
		else if(qu[i].op == 5) qu[i].x = read();
		qu[i].val = (qu[i].val % mod + mod) % mod;
	}
	ll t = read();
	for(ll i = 1;i <= t;++i) a[i] = read(),b[i] = read();
	for(ll i = 1;i <= t;++i)
	{
		for(ll j = 1;j <= q;++j)
		{
			ll num = ((a[i] + j * b[i]) % q + 1);
			ll tim = (i - 1) * q + j;
			calc(num,tim);
		}
	}
	printf("%lld\n",(ans % mod + mod) % mod);
}
上一篇:[SDOI2019] 热闹的聚会与尴尬的聚会


下一篇:一键生成dotnet5项目解决方案