Transformation（ HDU - 4578 ，多重懒惰标记线段树 + 思维）
一.题目链接：
HDU-4578
二.题目大意：
n 个数 a[1 ~ n].
现有 m 次 4 种操作.
1 l r c：a[l ~ r] 都 + c
2 l r c：a[l ~ r] 都 × c
3 l r c：a[l ~ r] 都变为 c
4 l r p：查询 
三.分析：
由上述公式便可得每次更新后的 [1, 3] 次幂的和.
之后可以设置 3 个懒惰标记 add，mul，rep
或者只设置 2 个 add，mul（rep 可由 add = c，mul = 0实现）
四.代码实现：
3 个懒惰标记：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;
const int M = (int)1e5;
const int mod = 10007;
struct node
{
int l;
int r;
ll add;
ll mul;
ll rep;
ll p[4];
}tree[M * 4 + 5];
ll ans;
void build(int k, int l, int r)
{
tree[k].l = l;
tree[k].r = r;
tree[k].add = 0;
tree[k].mul = 1;
tree[k].rep = 0;
tree[k].p[3] = tree[k].p[2] = tree[k].p[1] = 0;
if(l == r)
return;
int mid = (l + r) / 2;
build(k * 2, l, mid);
build(k * 2 + 1, mid + 1, r);
}
void push(int k)
{
if(tree[k].rep)
{
tree[k * 2].rep = tree[k * 2 + 1].rep = tree[k].rep;
tree[k * 2].mul = tree[k * 2 + 1].mul = 0;
tree[k * 2].add = tree[k * 2 + 1].add = tree[k].rep;
tree[k * 2].p[3] = tree[k].rep * tree[k].rep * tree[k].rep % mod * (tree[k * 2].r - tree[k * 2].l + 1) % mod;
tree[k * 2].p[2] = tree[k].rep * tree[k].rep % mod * (tree[k * 2].r - tree[k * 2].l + 1) % mod;
tree[k * 2].p[1] = tree[k].rep % mod * (tree[k * 2].r - tree[k * 2].l + 1) % mod;
tree[k * 2 + 1].p[3] = tree[k].rep * tree[k].rep * tree[k].rep % mod * (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1) % mod;
tree[k * 2 + 1].p[2] = tree[k].rep * tree[k].rep % mod * (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1) % mod;
tree[k * 2 + 1].p[1] = tree[k].rep % mod * (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1) % mod;
tree[k].rep = 0;
}
if(tree[k].mul != 1)
{
tree[k * 2].add = tree[k * 2].add * tree[k].mul % mod;
tree[k * 2 + 1].add = tree[k * 2 + 1].add * tree[k].mul % mod;
tree[k * 2].mul = tree[k * 2].mul * tree[k].mul % mod;
tree[k * 2 + 1].mul = tree[k * 2 + 1].mul * tree[k].mul % mod;
tree[k * 2].p[3] = tree[k * 2].p[3] * tree[k].mul % mod * tree[k].mul % mod * tree[k].mul % mod;
tree[k * 2].p[2] = tree[k * 2].p[2] * tree[k].mul % mod * tree[k].mul % mod;
tree[k * 2].p[1] = tree[k * 2].p[1] * tree[k].mul % mod;
tree[k * 2 + 1].p[3] = tree[k * 2 + 1].p[3] * tree[k].mul % mod * tree[k].mul % mod * tree[k].mul % mod;
tree[k * 2 + 1].p[2] = tree[k * 2 + 1].p[2] * tree[k].mul % mod * tree[k].mul % mod;
tree[k * 2 + 1].p[1] = tree[k * 2 + 1].p[1] * tree[k].mul % mod;
tree[k].mul = 1;
}
if(tree[k].add)
{
tree[k * 2].add = (tree[k * 2].add + tree[k].add) % mod;
tree[k * 2 + 1].add = (tree[k * 2 + 1].add + tree[k].add) % mod;
tree[k * 2].p[3] = (tree[k * 2].p[3] + 3 * tree[k].add * tree[k * 2].p[2] % mod + 3 * tree[k].add * tree[k].add % mod * tree[k * 2].p[1] % mod + tree[k].add * tree[k].add * tree[k].add % mod * (tree[k * 2].r - tree[k * 2].l + 1) % mod) % mod;
tree[k * 2].p[2] = (tree[k * 2].p[2] + 2 * tree[k].add * tree[k * 2].p[1] + tree[k].add * tree[k].add % mod * (tree[k * 2].r - tree[k * 2].l + 1) % mod) % mod;
tree[k * 2].p[1] = (tree[k * 2].p[1] + tree[k].add * (tree[k * 2].r - tree[k * 2].l + 1) % mod) % mod;
tree[k * 2 + 1].p[3] = (tree[k * 2 + 1].p[3] + 3 * tree[k].add * tree[k * 2 + 1].p[2] % mod + 3 * tree[k].add * tree[k].add % mod * tree[k * 2 + 1].p[1] % mod + tree[k].add * tree[k].add * tree[k].add % mod * (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1) % mod) % mod;
tree[k * 2 + 1].p[2] = (tree[k * 2 + 1].p[2] + 2 * tree[k].add * tree[k * 2 + 1].p[1] + tree[k].add * tree[k].add % mod * (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1) % mod) % mod;
tree[k * 2 + 1].p[1] = (tree[k * 2 + 1].p[1] + tree[k].add * (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1) % mod) % mod;
tree[k].add = 0;
}
}
void interver(int k, int l, int r, int a, int b, ll c, int dir)
{
if(l >= a && r <= b)
{
if(dir == 1)
{
tree[k].add = (tree[k].add + c) % mod;
tree[k].p[3] = (tree[k].p[3] + 3 * c * tree[k].p[2] % mod + 3 * c * c % mod * tree[k].p[1] % mod + c * c * c % mod * (tree[k].r - tree[k].l + 1) % mod) % mod;
tree[k].p[2] = (tree[k].p[2] + 2 * c % mod * tree[k].p[1] % mod + c * c % mod * (tree[k].r - tree[k].l + 1) % mod) % mod;
tree[k].p[1] = (tree[k].p[1] + c * (tree[k].r - tree[k].l + 1) % mod) % mod;
return;
}
else if(dir == 2)
{
tree[k].add = tree[k].add * c % mod;
tree[k].mul = tree[k].mul * c % mod;
tree[k].p[3] = tree[k].p[3] * c % mod * c % mod * c % mod;
tree[k].p[2] = tree[k].p[2] * c % mod * c % mod;
tree[k].p[1] = tree[k].p[1] * c % mod;
return;
}
else if(dir == 3)
{
tree[k].add = 0;
tree[k].mul = 1;
tree[k].rep = c;
tree[k].p[3] = c * c * c % mod * (tree[k].r - tree[k].l + 1) % mod;
tree[k].p[2] = c * c % mod * (tree[k].r - tree[k].l + 1) % mod;
tree[k].p[1] = c * (tree[k].r - tree[k].l + 1) % mod;
return;
}
}
push(k);
int mid = (l + r) / 2;
if(a <= mid)
interver(k * 2, l, mid, a, b, c, dir);
if(mid < b)
interver(k * 2 + 1, mid + 1, r, a, b, c, dir);
tree[k].p[3] = (tree[k * 2].p[3] + tree[k * 2 + 1].p[3]) % mod;
tree[k].p[2] = (tree[k * 2].p[2] + tree[k * 2 + 1].p[2]) % mod;
tree[k].p[1] = (tree[k * 2].p[1] + tree[k * 2 + 1].p[1]) % mod;
}
void query(int k, int l, int r, int a, int b, ll c)
{
if(l >= a && r <= b)
{
ans = (ans + tree[k].p[c]) % mod;
return;
}
push(k);
int mid = (l + r) / 2;
if(a <= mid)
query(k * 2, l, mid, a, b, c);
if(mid < b)
query(k * 2 + 1, mid + 1, r, a, b, c);
tree[k].p[3] = (tree[k * 2].p[3] + tree[k * 2 + 1].p[3]) % mod;
tree[k].p[2] = (tree[k * 2].p[2] + tree[k * 2 + 1].p[2]) % mod;
tree[k].p[1] = (tree[k * 2].p[1] + tree[k * 2 + 1].p[1]) % mod;
}
int main()
{
int n, m;
while(~scanf("%d %d", &n, &m))
{
if(n + m == 0)
break;
build(1, 1, n);
while((m--) > 0)
{
int dir, l, r;
ll c;
scanf("%d %d %d %lld", &dir, &l, &r, &c);
if(dir <= 3)
interver(1, 1, n, l, r, c, dir);
else
{
ans = 0;
query(1, 1, n, l, r, c);
printf("%lld\n", ans);
}
}
}
return 0;
}
2 个懒惰标记：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;
const int M = (int)1e5;
const int mod = 10007;
struct node
{
int l;
int r;
ll p[4];
ll mul;
ll add;
}tree[M * 4 + 5];
ll ans;
void build(int k, int l, int r)
{
tree[k].l = l;
tree[k].r = r;
tree[k].mul = 1;
tree[k].add = 0;
tree[k].p[1] = tree[k].p[2] = tree[k].p[3] = 0;
if(l == r)
return;
int mid = (l + r) / 2;
build(k * 2, l, mid);
build(k * 2 + 1, mid + 1, r);
}
void push(int k)
{
tree[k * 2].mul = tree[k * 2].mul * tree[k].mul % mod;
tree[k * 2 + 1].mul = tree[k * 2 + 1].mul * tree[k].mul % mod;
tree[k * 2].p[3] = tree[k].mul * tree[k].mul * tree[k].mul % mod * tree[k * 2].p[3] % mod;
tree[k * 2].p[2] = tree[k].mul * tree[k].mul % mod * tree[k * 2].p[2] % mod;
tree[k * 2].p[1] = tree[k].mul * tree[k * 2].p[1] % mod;
tree[k * 2 + 1].p[3] = tree[k].mul * tree[k].mul * tree[k].mul % mod * tree[k * 2 + 1].p[3] % mod;
tree[k * 2 + 1].p[2] = tree[k].mul * tree[k].mul % mod * tree[k * 2 + 1].p[2] % mod;
tree[k * 2 + 1].p[1] = tree[k].mul * tree[k * 2 + 1].p[1] % mod;
tree[k * 2].add = (tree[k * 2].add * tree[k].mul % mod + tree[k].add) % mod;
tree[k * 2 + 1].add = (tree[k * 2 + 1].add * tree[k].mul % mod + tree[k].add) % mod;
tree[2 * k].p[3] = (tree[2 * k].p[3] + 3 * tree[k].add * tree[2 * k].p[2] % mod + 3 * tree[k].add % mod * tree[k].add % mod * tree[2 * k].p[1] % mod + (tree[2 * k].r - tree[2 * k].l + 1) % mod * tree[k].add % mod * tree[k].add % mod * tree[k].add % mod) % mod;
tree[2 * k].p[2] = (tree[2 * k].p[2] + 2 * tree[k].add % mod * tree[2 * k].p[1] % mod + (tree[2 * k].r - tree[2 * k].l + 1) % mod * tree[k].add % mod * tree[k].add % mod) % mod;
tree[2 * k].p[1] = (tree[2 * k].p[1] + (tree[2 * k].r - tree[2 * k].l + 1) % mod * tree[k].add % mod) % mod;
tree[k * 2 + 1].p[3] = (tree[k * 2 + 1].p[3] + 3 * tree[k].add * tree[k * 2 + 1].p[2] % mod + 3 * tree[k].add % mod * tree[k].add % mod * tree[k * 2 + 1].p[1] % mod + (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1) % mod * tree[k].add % mod * tree[k].add % mod * tree[k].add % mod) % mod;
tree[k * 2 + 1].p[2] = (tree[k * 2 + 1].p[2] + 2 * tree[k].add % mod * tree[k * 2 + 1].p[1] % mod + (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1) % mod * tree[k].add % mod * tree[k].add % mod) % mod;
tree[k * 2 + 1].p[1] = (tree[k * 2 + 1].p[1] + (tree[k * 2 + 1].r - tree[k * 2 + 1].l + 1) % mod * tree[k].add % mod) % mod;
tree[k].add = 0;
tree[k].mul = 1;
}
void interver(int k, int l, int r, int a, int b, ll c, int dir)
{
if(l >= a && r <= b)
{
if(dir == 1)
{
tree[k].add = (tree[k].add + c) % mod;
tree[k].p[3] = (tree[k].p[3] + 3 * c * tree[k].p[2] % mod + 3 * c % mod * c % mod * tree[k].p[1] % mod + (tree[k].r - tree[k].l + 1) % mod * c % mod * c % mod * c % mod) % mod;
tree[k].p[2] = (tree[k].p[2] + 2 * c % mod * tree[k].p[1] % mod + (tree[k].r - tree[k].l + 1) % mod * c % mod * c % mod) % mod;
tree[k].p[1] = (tree[k].p[1] + (tree[k].r - tree[k].l + 1) % mod * c % mod) % mod;
return;
}
else if(dir == 2)
{
tree[k].add = tree[k].add * c % mod;
tree[k].mul = tree[k].mul * c % mod;
tree[k].p[3] = c * c * c % mod * tree[k].p[3] % mod;
tree[k].p[2] = c * c % mod * tree[k].p[2] % mod;
tree[k].p[1] = c * tree[k].p[1] % mod;
return;
}
else if(dir == 3)
{
tree[k].add = c;
tree[k].mul = 0;
tree[k].p[3] = c * c * c % mod * (tree[k].r - tree[k].l + 1) % mod;
tree[k].p[2] = c * c % mod * (tree[k].r - tree[k].l + 1) % mod;
tree[k].p[1] = c * (tree[k].r - tree[k].l + 1) % mod;
return;
}
}
push(k);
int mid = (l + r) / 2;
if(a <= mid)
interver(k * 2, l, mid, a, b, c, dir);
if(mid < b)
interver(k * 2 + 1, mid + 1, r, a, b, c, dir);
tree[k].p[3] = (tree[k * 2].p[3] + tree[k * 2 + 1].p[3]) % mod;
tree[k].p[2] = (tree[k * 2].p[2] + tree[k * 2 + 1].p[2]) % mod;
tree[k].p[1] = (tree[k * 2].p[1] + tree[k * 2 + 1].p[1]) % mod;
}
void query(int k, int l, int r, int a, int b, int c)
{
if(l >= a && r <= b)
{
ans = (ans + tree[k].p[c]) % mod;
return;
}
push(k);
int mid = (l + r) / 2;
if(a <= mid)
query(k * 2, l, mid, a, b, c);
if(mid < b)
query(k * 2 + 1, mid + 1, r, a, b, c);
tree[k].p[3] = (tree[k * 2].p[3] + tree[k * 2 + 1].p[3]) % mod;
tree[k].p[2] = (tree[k * 2].p[2] + tree[k * 2 + 1].p[2]) % mod;
tree[k].p[1] = (tree[k * 2].p[1] + tree[k * 2 + 1].p[1]) % mod;
}
int main()
{
int n, m;
while(~scanf("%d %d", &n, &m))
{
if(n + m == 0)
break;
build(1, 1, n);
while((m--) > 0)
{
int dir, x, y;
ll c;
scanf("%d %d %d %lld", &dir, &x, &y, &c);
if(dir <= 3)
interver(1, 1, n, x, y, c, dir);
else if(dir == 4)
{
ans = 0;
query(1, 1, n, x, y, c);
printf("%lld\n", ans);
}
}
}
return 0;
}
投递阿里巴巴控股集团等公司9个岗位 >