这题杯具的写了一下午,真是太菜了。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
int const N= 100010;
int n, m;
struct Node{
int Lx1, Rx1, Ax1;
int Lx0, Rx0, Ax0;
int op1, op2, op3;
int num;
};
Node tb[N<<2];
int dat[N];
void inline toRoot( int rt, int L, int R ){
int mid= (L+ R)>>1;
tb[rt].num= tb[rt<<1].num+ tb[rt<<1|1].num;
tb[rt].Ax1= max( tb[rt<<1].Ax1, tb[rt<<1|1].Ax1 );
if( tb[rt<<1].Lx1== mid- L+ 1 ) tb[rt].Lx1= tb[rt<<1].Lx1+ tb[rt<<1|1].Lx1;
else tb[rt].Lx1= tb[rt<<1].Lx1;
if( tb[rt<<1|1].Rx1== R- mid ) tb[rt].Rx1= tb[rt<<1|1].Rx1+ tb[rt<<1].Rx1;
else tb[rt].Rx1= tb[rt<<1|1].Rx1;
tb[rt].Ax1= max( tb[rt<<1].Rx1+ tb[rt<<1|1].Lx1, tb[rt].Ax1 );
tb[rt].Ax0= max( tb[rt<<1].Ax0, tb[rt<<1|1].Ax0 );
if( tb[rt<<1].Lx0== mid- L+ 1 ) tb[rt].Lx0= tb[rt<<1].Lx0+ tb[rt<<1|1].Lx0;
else tb[rt].Lx0= tb[rt<<1].Lx0;
if( tb[rt<<1|1].Rx0== R- mid ) tb[rt].Rx0= tb[rt<<1|1].Rx0+ tb[rt<<1].Rx0;
else tb[rt].Rx0= tb[rt<<1|1].Rx0;
tb[rt].Ax0= max( tb[rt<<1].Rx0+ tb[rt<<1|1].Lx0, tb[rt].Ax0 );
}
void inline Down( int rt, int L, int R ){
int mid= (L+ R)>>1;
if( tb[rt].op1 ){
tb[rt<<1].op1= tb[rt<<1|1].op1= 1;
tb[rt<<1].op2= tb[rt<<1|1].op2= 0;
tb[rt<<1].op3= tb[rt<<1|1].op3= 0;
tb[rt<<1].Lx0= tb[rt<<1].Rx0= tb[rt<<1].Ax0= mid- L+ 1;
tb[rt<<1].Lx1= tb[rt<<1].Rx1= tb[rt<<1].Ax1= 0;
tb[rt<<1].num= 0;
tb[rt<<1|1].Lx0= tb[rt<<1|1].Rx0= tb[rt<<1|1].Ax0= R- mid;
tb[rt<<1|1].Lx1= tb[rt<<1|1].Rx1= tb[rt<<1|1].Ax1= 0;
tb[rt<<1|1].num= 0;
}
if( tb[rt].op2 ){
tb[rt<<1].op2= tb[rt<<1|1].op2= 1;
tb[rt<<1].op1= tb[rt<<1|1].op1= 0;
tb[rt<<1].op3= tb[rt<<1|1].op3= 0;
tb[rt<<1].Lx0= tb[rt<<1].Rx0= tb[rt<<1].Ax0= 0;
tb[rt<<1].Lx1= tb[rt<<1].Rx1= tb[rt<<1].Ax1= mid- L+ 1;
tb[rt<<1].num= mid- L+ 1;
tb[rt<<1|1].Lx0= tb[rt<<1|1].Rx0= tb[rt<<1|1].Ax0= 0;
tb[rt<<1|1].Lx1= tb[rt<<1|1].Rx1= tb[rt<<1|1].Ax1= R- mid;
tb[rt<<1|1].num= R- mid;
}
if( tb[rt].op3 ){
tb[rt<<1].op3= 1- tb[rt<<1].op3;
tb[rt<<1|1].op3= 1- tb[rt<<1|1].op3;
int x= tb[rt<<1].Lx0, y= tb[rt<<1].Rx0, z= tb[rt<<1].Ax0;
tb[rt<<1].Lx0= tb[rt<<1].Lx1;
tb[rt<<1].Rx0= tb[rt<<1].Rx1;
tb[rt<<1].Ax0= tb[rt<<1].Ax1;
tb[rt<<1].Lx1= x; tb[rt<<1].Rx1= y; tb[rt<<1].Ax1= z;
tb[rt<<1].num= mid- L+ 1- tb[rt<<1].num;
x= tb[rt<<1|1].Lx0, y= tb[rt<<1|1].Rx0, z= tb[rt<<1|1].Ax0;
tb[rt<<1|1].Lx0= tb[rt<<1|1].Lx1;
tb[rt<<1|1].Rx0= tb[rt<<1|1].Rx1;
tb[rt<<1|1].Ax0= tb[rt<<1|1].Ax1;
tb[rt<<1|1].Lx1= x; tb[rt<<1|1].Rx1= y; tb[rt<<1|1].Ax1= z;
tb[rt<<1|1].num= R- mid- tb[rt<<1|1].num;
}
tb[rt].op1= tb[rt].op2= tb[rt].op3= 0;
}
void build( int L, int R, int rt ){
tb[rt].op1= tb[rt].op2= tb[rt].op3= 0;
if( L== R ){
if( dat[L]== 1 ) {
tb[rt].Lx1= tb[rt].Rx1= tb[rt].Ax1= 1;
tb[rt].Lx0= tb[rt].Rx0= tb[rt].Ax0= 0;
tb[rt].num= 1;
}
else {
tb[rt].Lx1= tb[rt].Rx1= tb[rt].Ax1= 0;
tb[rt].Lx0= tb[rt].Rx0= tb[rt].Ax0= 1;
tb[rt].num= 0;
}
return;
}
int mid= (L+ R)>>1;
build( L, mid, rt<<1 );
build( mid+ 1, R, rt<<1|1 );
toRoot( rt, L, R );
}
void update( int x, int y, int d, int L, int R, int rt ){
if( L!= R ) Down( rt, L, R );
if( L== x && R== y ){
if( d== 1 ){
tb[rt].op1= 1;
tb[rt].Lx0= tb[rt].Rx0= tb[rt].Ax0= R- L+ 1;
tb[rt].Lx1= tb[rt].Rx1= tb[rt].Ax1= 0;
tb[rt].num= 0;
}
else if( d== 2 ){
tb[rt].op2= 1;
tb[rt].Lx0= tb[rt].Rx0= tb[rt].Ax0= 0;
tb[rt].Lx1= tb[rt].Rx1= tb[rt].Ax1= R- L+ 1;
tb[rt].num= R- L+ 1;
}
else if( d== 3 ){
tb[rt].op3= 1;
int a= tb[rt].Lx0, b= tb[rt].Rx0, c= tb[rt].Ax0;
tb[rt].Lx0= tb[rt].Lx1;
tb[rt].Rx0= tb[rt].Rx1;
tb[rt].Ax0= tb[rt].Ax1;
tb[rt].Lx1= a; tb[rt].Rx1= b; tb[rt].Ax1= c;
tb[rt].num= R- L+ 1- tb[rt].num;
}
return;
}
int mid= (L+ R)>>1;
if( y<= mid ) update( x, y, d, L, mid, rt<<1 );
else if( x> mid ) update( x, y, d, mid+ 1, R, rt<<1|1 );
else{
update( x, mid, d, L, mid, rt<<1 );
update( mid+ 1, y, d, mid+ 1, R, rt<<1|1 );
}
toRoot( rt, L, R );
}
int query( int x, int y, int d, int L, int R, int rt ){
if( L!= R ) Down( rt, L, R );
if( x== L && y== R ){
if( d== 4 ) return tb[rt].num;
else return tb[rt].Ax1;
}
int mid= (L+ R)>>1;
if( y<= mid ) return query( x, y, d, L, mid, rt<<1 );
else if( x> mid ) return query( x, y, d, mid+ 1, R, rt<<1|1 );
else{
int a= 0, b= 0;
if( d== 4 ){
a= query( x, mid, d, L, mid, rt<<1 );
b= query( mid+ 1, y, d, mid+ 1, R, rt<<1|1 );
return a+ b;
}
else{
a= query( x, mid, d, L, mid, rt<<1 );
b= query( mid+ 1, y, d, mid+ 1, R, rt<<1|1 );
int c= min( mid- x+ 1, tb[rt<<1].Rx1 )+ min( y- mid, tb[rt<<1|1].Lx1 );
return max( a, max( b, c ) );
}
}
}
int main(){
int test;
scanf("%d",&test );
while( test-- ){
scanf("%d%d",&n,&m );
for( int i= 1; i<= n; ++i ) scanf("%d", dat+ i );
build( 1, n, 1 );
for( int i= 0; i< m; ++i ){
int op, a, b;
scanf("%d%d%d", &op, &a, &b );
a++; b++; op++;
if( op<= 3 )
update( a, b, op, 1, n, 1 );
else
printf("%d\n", query( a, b, op, 1, n, 1 ) );
}
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...
标题与描述均提到了“hdu 1166线段树”,这表明文章的核心是关于线段树在解决特定问题中的应用。线段树是一种数据结构,主要用于处理区间查询和更新操作,尤其是在大规模数据集上。在本例中,通过分析给定的部分代码...
### 线段树知识点详解 #### 一、线段树基本概念与应用 线段树是一种二叉树数据结构,常用于处理区间查询或区间更新的问题。它将一个线性序列分割成多个不连续的段,每一个节点代表一个区间,并且通过递归的方式将...
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
这篇博客“线段树入门学习(兼解HDU1754)”旨在帮助初学者理解线段树的基本概念,并通过解决HDU1754题目来实践其应用。 线段树的核心思想是将一个区间分解成多个子区间,然后对每个子区间进行预处理,存储区间的信息...
- **HDU 3074**:简单的线段树题目,要求求解区间乘积。在节点中维护区间乘积信息即可。 - **BZOJ 1798**:涉及到区间乘法和加法的操作,需要求解区间和。在线段树中需要支持这两种操作,并正确处理它们之间的关系...
### 线段树经典知识点解析 #### 一、线段树简介与代码风格 **线段树**是一种用于高效处理区间查询与更新操作的数据结构。它可以用来解决一系列与区间有关的问题,例如区间求和、区间最值等问题。相较于其他数据...
在IT行业中,"Number Sequence"通常指的是在特定系统或应用中用于生成自动递增或递减的数字序列。这些序列可以用于唯一标识记录、订单号、发票号等,确保数据的唯一性和可追踪性。在Microsoft Dynamics AX(现称为...
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
**线段树(Segment Tree)**是一种用于处理区间查询和修改的高效数据结构。在这个问题中,线段树的每个节点存储的信息不仅仅是区间内的和,而是区间内不同数字的和。线段树的每个节点包含以下信息: 1. `a` 和 `b`...
2. **线段树**:线段树是一种数据结构,用于高效地处理区间查询和更新操作。它可以实时维护一个区间内的信息,如求和、最大值或最小值。线段树在处理动态区间问题时非常有效,如在数组上进行区间加法、区间求和等...
3. **数据结构**:数组、链表、栈、队列、树(二叉树、平衡树如AVL和红黑树)、图(邻接矩阵、邻接表、最小生成树、拓扑排序等)。 4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **...
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
总结来说,"二叉搜索树练习 HDU3791"是一道关于二叉搜索树操作的编程题,可能需要实现插入、删除、查找等基本操作,并通过分析`Main.java`源码来理解和解决问题。同时,可能需要借助各种工具进行调试和测试,以确保...
《HDU5667 Sequence:递推序列的矩阵快速幂解决方案》 在解决计算机科学中的数学问题时,特别是涉及到大规模数值计算时,高效的算法至关重要。HDU5667 "Sequence" 这一问题就是一个典型的例子,它要求处理一个递推...
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...