题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4578
题目大意:n个数(初始为0)m个操作,操作类型有4种,操作1把区间的每个数+a,操作2把区间的每个数*a.,操作3把区间的每个数=a,操作4,查询区间每个数p次方的和(1<=p<=3)
解:
线段树解决,考虑的问题有两个:
1、赋值操作一定放在前面,然后有 先+后* 和 先*后+ 效果不一样
2、p次方和
对于问题一,采用先*后+的方式,这样在加入一个乘法标记的时候只用给之前的加标记乘上新标记的数即可
对于问题二,把(a+b)^2 和 (a+b)^3 展开,就知道怎么处理了
/*
* Problem:
* Author: SHJWUDP
* Created Time: 2015/11/3 星期二 15:20:05
* File Name: 1001.cpp
* State:
* Memo:
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <list> using namespace std; const int MOD=1e4+; struct SegmentTree {
struct Node {
vector<long long> sum;
vector<long long> delay;
Node():sum(), delay(){ delay[]=; }
void relax() {
for(auto & x : sum) x%=MOD;
for(auto & x : delay) x%=MOD;
}
};
int n;
vector<Node> c;
SegmentTree(int _n):n(_n),c(_n<<){}
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
void deal(Node & o, pair<int, int> p, int range) {
auto & d=o.delay;
long long b1=p.second, b2=b1*b1, b3=b2*b1;
switch(p.first) {
case :
{
long long a1=o.sum[], a2=o.sum[];
o.sum[]+=*a1*b2+*a2*b1+b3*range;
o.sum[]+=*a1*b1+b2*range;
o.sum[]+=b1*range;
d[]+=b1;
break;
}
case :
o.sum[]*=b3;
o.sum[]*=b2;
o.sum[]*=b1;
d[]*=b1;
d[]*=b1;
break;
case :
o.sum[]=b3*range;
o.sum[]=b2*range;
o.sum[]=b1*range;
d[]=; d[]=;
d[]=b1;
break;
}
o.relax();
}
void pushDown(int l, int m, int r, int rt) {
for(int i=; i>=; --i) {
if(!c[rt].delay[i]) continue;
if(i== && c[rt].delay[i]==) continue;
deal(c[rt<<], {i, c[rt].delay[i]}, m-l+);
deal(c[rt<<|], {i, c[rt].delay[i]}, r-m);
}
c[rt].delay={, , };
}
void pushUp(int rt) {
for(int i=; i<; ++i) {
c[rt].sum[i]=(c[rt<<].sum[i]+c[rt<<|].sum[i])%MOD;
}
}
void update(int L, int R, pair<int, int> x, int l, int r, int rt) {
if(L<=l && r<=R) {
deal(c[rt], x, r-l+);
} else {
int m=(l+r)>>;
pushDown(l, m, r, rt);
if(L<=m) update(L, R, x, lson);
if(m<R) update(L, R, x, rson);
pushUp(rt);
}
}
int query(int L, int R, int x, int l, int r, int rt) {
if(L<=l && r<=R) {
return c[rt].sum[x];
} else {
int m=(l+r)>>;
pushDown(l, m, r, rt);
int ret=;
if(L<=m) ret=query(L, R, x, lson);
if(m<R) ret=(ret+query(L, R, x, rson))%MOD;
return ret;
}
}
}; int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif
int n, m;
while(scanf("%d%d", &n, &m), n||m) {
SegmentTree st(n);
while(m--) {
int op, a, b, c;
scanf("%d%d%d%d", &op, &a, &b, &c);
--a; --b;
// cout<<"<----------------->"<<endl;
if(op==) {
printf("%d\n", st.query(a, b, c-, , st.n-, ));
} else {
st.update(a, b, {op-, c}, , st.n-, );
}
}
}
return ;
}
hdu4578 Transformation的更多相关文章
-
HDU-4578 Transformation(线段树的多种区间操作)
http://acm.hdu.edu.cn/showproblem.php?pid=4578 Time Limit: 15000/8000 MS (Java/Others) Memory Lim ...
-
【HDU4578 Transformation】线段树
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4578 题意:有一个序列,有四种操作: 1:区间[l,r]内的数全部加c. 2:区间[l,r]内的数全部 ...
-
HDU4578 Transformation 线段树
这个题让我重新学习了加 乘 在区间的操作 题解:http://blog.csdn.net/guognib/article/details/25324025?utm_source=tuicool& ...
-
HDU4578 Transformation【线段树】
<题目链接> <转载于 >>> > 题目大意: 有一个序列,有四种操作: 1:区间[l,r]内的数全部加c. 2:区间[l,r]内的数全部乘c. 3:区间[l ...
-
HDU4578 Transformation (多操作线段树)
传送门 终于过了这道题.. 要注意标记之间的影响,和add操作时更新求和的顺序. same 区间每个数设置为x标记 mult 区间每个数乘x标记 add 区间每个数加x标记 ①:当打same标记时 ...
-
HDU4578 Transformation(多标记线段树)题解
题意: 操作有:\(1\).区间都加\(a\):\(2\).区间都乘\(a\):\(3\).区间都重置成\(a\):\(4\).询问区间幂次和\(\sum_{i=l}^rnum[i]^p(p\in\{ ...
-
Transformation(线段树+HDU4578+多种操作+鬼畜的代码)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4578 题目: 题意:n个数初始值为0,进行四种操作:1.将区间内的数字加c:2.将区间内的数字乘c:3 ...
-
(七)Transformation和action详解-Java&;Python版Spark
Transformation和action详解 视频教程: 1.优酷 2.YouTube 什么是算子 算子是RDD中定义的函数,可以对RDD中的数据进行转换和操作. 算子分类: 具体: 1.Value ...
-
线性分式变换(linear fractional transformation)
线性分式变换(linear fractional transformation)的名称来源于其定义的形式:(ax+b)/(cx+d),其中分子分母是线性的,然后最外层是一个分式形式,所以叫做这个名字, ...
随机推荐
-
在ASP.NET Core中使用百度在线编辑器UEditor
在ASP.NET Core中使用百度在线编辑器UEditor 0x00 起因 最近需要一个在线编辑器,之前听人说过百度的UEditor不错,去官网下了一个.不过服务端只有ASP.NET版的,如果是为了 ...
-
Vue.js&mdash;&mdash;60分钟组件快速入门(下篇)
概述 上一篇我们重点介绍了组件的创建.注册和使用,熟练这几个步骤将有助于深入组件的开发.另外,在子组件中定义props,可以让父组件的数据传递下来,这就好比子组件告诉父组件:"嘿,老哥,我开 ...
-
docker定制化镜像的构建及基于该定制的镜像创建容器
1.在项目里创建Dockerfile(注意大小写)文件,执行构建命令:docker build -t tiny-node-1 /root/tiny-node-docker 其中tiny-node ...
-
Nexus3.0.0+Maven的使用(二)
因为Nexus3.0.0与Nexus2.X系列的差别很大,所以本章节我大概讲解下Nexus3.0.0的功能使用. 1.功能介绍 1.1 Browse Server Content 1.1.1 Se ...
-
动态代理模式和AOP探究
java强大的反射机制给动态代理带来了可能.能够*穿梭在类与方法之间.简直神通广大. 动态代理的一个小例子,顺便看看神奇的AOP是如何实现的.代码如下: 首先声明的是一个接口Dog类 package ...
-
mysql help
1.一般情况,不知道命令的使用方法,有三种办法: a. --help 是命令的一个选项,介绍命令的使用方法.mysql --help 或者mysql -? b. man 对命令的详细解释,man my ...
-
关于.net 对.manifest清单文件查找缓存的猜想
问题背景: winform调用unity web player 插件. 按如下操作: ,编译后会生成.manifest清单文件: 通过清单内容可以看出程序在运行时是按照以上信息来查找ActiveX控件 ...
-
使用VisualStudio发布ASP.NET网站
1.右击网站点击“发布网站” 2.选择或导入发布配置文件.→新建配置文件. 3.输入名称test.→点击确定. 4.发布方法选择文件系统. 5.选择目标位置.→点击下一步 6.文件发布选项选择三个选项 ...
-
初学Python(八)——迭代
初学Python(八)——迭代 初学Python,主要整理一些学习到的知识点,这次是迭代. # -*- coding:utf-8 -*- from collections import Iterabl ...
-
HBase新的客户端接口
最近学习接触HBase的东西,看了<Habase in Action>,但里面关于HBase接口都是过时的接口,以下为HBase新的客户端接口: package com.n10k; imp ...