线段树好题！！！！
咕咕了挺久的一道题目，很早之前就想写了，今天终于找了个时间A掉了。
给定一个 \(1\) 到 \(n\) 的排列，有 \(m\) 次操作，分两种类型。
1.0 l r表示将下标在 \([l, r]\) 区间中的数升序排序。
2.1 l r表示将下标在 \([l, r]\) 区间中的数降序排序。
给定一个数 \(q\) 询问最后 \(q\) 位置上的数。
看到数据范围，发现前 \(30\) 分是可以暴力的，这里不多赘述。
注意到 \(n,m\leqslant 10^5\) ,优先考虑 \(O(nlogn)\) 或 \(O(n \sqrt n)\) 做法。对一个序列进行操作，自然想到，线段树，但是线段树不支持区间排序那怎么办呢。
考虑对一段 \(01\) 串做排序，显然排完序后会变成 \(00011\) 或 \(11100\) 这种形式，可以用线段树的区间推平和求和操作来完成。
但是原序列不是 \(01\) 串，我们就要把它转换成 \(01\) 串。
可以选取一个基准数，让原序列大于等于这个数的都变成 \(1\) ，其他的都是 \(0\) 就能解决这个问题了。
如果操作完之后 \(q\) 上的是 \(1\) ，说明答案至少是大于等于这个基准数的，所以二分就行了。
总复杂度 \(O(n log^2n)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m, pos;
int a[N];
struct question
{
int op, l, r;
} Q[N];
struct segment_tree
{
int l, r, val, tag;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define val(x) tr[x].val
#define tag(x) tr[x].tag
} tr[N << 2];
void pushup(int x)
{
val(x) = val(x << 1) + val(x << 1 | 1);
}
void pushdown(int x)
{
if(tag(x) == -1) return;
val(x << 1) = (r(x << 1) - l(x << 1) + 1) * tag(x);
tag(x << 1) = tag(x);
val(x << 1 | 1) = (r(x << 1 | 1) - l(x << 1 | 1) + 1) * tag(x);
tag(x << 1 | 1) = tag(x);
tag(x) = -1;
}
void build(int l, int r, int x, int v)
{
l(x) = l, r(x) = r, tag(x) = -1, val(x) = 0;
if(l == r)
{
val(x) = (a[l] >= v);
return;
}
int mid = l + r >> 1;
build(l, mid, x << 1, v), build(mid + 1, r, x << 1 | 1, v);
pushup(x);
}
void update(int l, int r, int x, int v)
{
if(l <= l(x) && r(x) <= r)
{
tag(x) = v;
val(x) = (r(x) - l(x) + 1) * v;
return;
}
pushdown(x);
int mid = l(x) + r(x) >> 1;
if(l <= mid) update(l, r, x << 1, v);
if(r > mid) update(l, r, x << 1 | 1, v);
pushup(x);
}
int query(int l, int r, int x)
{
if(l <= l(x) && r(x) <= r) return val(x);
pushdown(x);
int mid = l(x) + r(x) >> 1, res = 0;
if(l <= mid) res += query(l, r, x << 1);
if(r > mid) res += query(l, r, x << 1 | 1);
return res;
}
int check(int v)
{
build(1, n, 1, v);
for(int i = 1;i <= m;i ++)
{
int l = Q[i].l, r = Q[i].r, op = Q[i].op;
int sum = query(l, r, 1);
if(sum == 0) continue;
update(l, r, 1, 0);
if(op == 0) update(r - sum + 1, r, 1, 1);
else update(l, l + sum - 1, 1, 1);
}
return query(pos, pos, 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1;i <= n;i ++) cin >> a[i];
for(int i = 1;i <= m;i ++) cin >> Q[i].op >> Q[i].l >> Q[i].r;
cin >> pos;
int l = 1, r = n, res;
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid)) l = mid + 1, res = mid;
else r = mid - 1;
}
cout << res << '\n';
return 0;
}
编辑:更改了标题。我对两个部分是否相同不太感兴趣，而是如果它们在一定的公差范围内彼此共线。如果是这样，那么这些线应该聚集在一起作为一个单独的线段。编辑:我想有一个简短的说法:我试图以一种有效的方式将相似的线段聚集在一起。假设我有线段f(fx0,fy0)和(fx1,fy1)和g(gx0,gy0)和(gx1,gy1)这些来自计算机视觉算法边缘检测器之类的东西，在某些情况下，两条线基本相同，但由于像素容差而被视为两条不同的线。有几种情况f和g共享完全相同的端点，例如:f=(0,0),(10,10)g=(0,0),(10,10)f和g共享大致相同的端点和大致相同的长度，例如:f=(0,0.01
这是一道简单题题目来自：https://leetcode.cn/problems/two-sum/题目给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。提示：22nums.length104−109−109nums[i]109−109−109target109只会存在一个有效答案进阶：你可以想出一个时间复杂度小于O(n2)O(n^2)O(n2)的算法吗？示例1：输入：nums=[2,7,11,15],targe
蓝桥杯第十四届蓝桥杯模拟赛第三期考场应对攻略（C/C++）真题可以去此处寻找https://blog.csdn.net/weixin_46239370/article/details/105464885?spm=1001.2014.3001.5506考前准备考前五分钟，开十个源文件，并把头文件等必须写的部分写出来，写完的程序一定要有顺序地保留万能头可以尝试开一下#include试题1：问题描述请找到一个大于2022的最小数，这个数转换成十六进制之后，所有的数位（不含前导0）都为字母（A到F）。请将这个数的十进制形式作为答案提交。答案提交这是一道结果填空的题，你只需要算出结果后提交即可。本题的结
我想画一个点，大约1秒后我想画下一个点。这是否可能:我已经试过了:functionsimulate(i){setTimeout(function(){drawPoint(vis,i,i);},1000);}for(vari=1;i不幸的是，这是行不通的。它只是立即绘制整条线。 最佳答案 这是行不通的，因为for循环将立即运行到结束，setTimeouts将被同时调度，所有函数将同时触发。取而代之的是，这样做:vari=1;(functionloop(){if(i++>200)return;setTimeout(function(){
我正在使用JavaScript将html导出到Excelxls文件，如下面的演示所示:http://js.do/sun21170/84913.我使用GoogleChrome来运行这个演示，但它也应该在Edge或IE或FireFox中运行。问题是，当我在Excel2016中打开导出的文件时，它显示没有任何边框，即使导出的html中有CSS来显示边框。问题:有没有办法在Excel中打开html文件时显示边框？在Excel中打开的相同html，在浏览器中呈现带有边框，因此边框的CSS是正确的。演示在http://js.do/sun21170/84913还显示了保存在Excel文件中的html
好吧，这个问题之前已经被问过很多次了——但是Youtube似乎每隔一天就改变一次。我找不到强制Youtube嵌入从头开始播放高清源的方法。切换到高清总是在5-10秒后发生。(不再)有效的方法:将&hd=1参数添加到iframesrc将&vd=hd720或&vd=hd1080参数添加到iframesrc。此处描述:Forceyoutubeembedtostartin720p在html嵌入代码中将iframe尺寸更改为width="1280"heigh="720"，然后使用CSS将iframe向下/向上缩放到父div。此处描述:http://thenewcode.com/717/Force
我使用以下示例来测试Babel和es2016预设的尾调用递归:'usestrict';try{functionr(n){if(n%5000===0)console.log(`reachedadepthof${n}`);r(n+1);}r(0);}catch(e){if(!(einstanceofRangeError))throwe;elseconsole.log('stackblown');}我的package.json文件是:{"name":"tail-call-optimization","version":"1.0.0","description":"","main":"inde
我需要在自动创建的Ionic项目中从2个空格的缩进样式切换到4个空格的缩进样式。我在MacOSX上运行WebStorm2016.1。我已经尝试过改变:网络Storm|偏好|代码风格|JavaScript|制表符和缩进并尝试调整缩进大小、制表符大小、使用制表符等...但似乎没有任何变化对现有(和新的)JavaScript文件产生影响。关于如何实现它的任何想法？某些常规设置可能会阻止此更改生效吗？ 最佳答案 您的项目中是否有.editorconfig文件？那里的设置将覆盖您的代码样式设置(这是预期的行为——这是EditorConfig插
没有测评，不知道对不对，仅仅过样例而已试题A:日期统计本题总分：5分【问题描述】小蓝现在有一个长度为100的数组，数组中的每个元素的值都在0到9的范围之内。数组中的元素从左至右如下所示：5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533现在他想要从这个数组中寻找一些满足以下条件的子序列： 1.子序列的长度为8； 2.这个子序列可以按照下标顺序组成一个yyyymmdd格式的日期，并且要求这个日期是2023年中的某一天的日期，例如202309
如果您采取以下措施:vars="2/8888/2016";vard=newDate(s);alert(d);在Chrome中，您将获得:InvalidDate但是在IE和Firefox中，你会得到:FriJun01204000:00:00GMT-0500(CentralDaylightTime)似乎只是将2月1日增加了8888天。相反，我希望该日期被视为无效。有没有办法让FireFox和IE认为这个日期字符串无效？ 最佳答案 简答:这是您提到的浏览器的不当行为。您必须自行检查日期格式是否正确。但这很简单，我建议采用这种方法:拆分年份