题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3671

原来256M是可以开两个3e7的数组的;

因为答案只有 n+m-1 个数,所以暴力判断能否放即可,不用线段树;

然而 O(n) 判断 O(1) 修改和 O(1) 判断 O(n) 修改是不同的。呵呵。

代码如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const xn=,xxn=,xm=5e4+;
int n,m,t[xxn],ps[xxn],mn[xn],mx[xn];
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int mnn(int x,int y){return x<y?x:y;}
int mxx(int x,int y){return x<y?y:x;}
int main()
{
int xx=rd(),a=rd(),b=rd(),c=rd(),d=rd();
n=rd(); m=rd(); int Q=rd();
for(int i=;i<=n*m;i++)t[i]=i;
for(int i=;i<=n*m;i++)
{
xx=((ll)a*xx*xx+(ll)b*xx+c)%d;//!%d
swap(t[i],t[xx%i+]);
}
for(int i=,u,v;i<=Q;i++)u=rd(),v=rd(),swap(t[u],t[v]);
for(int i=;i<=n*m;i++)ps[t[i]]=i;
for(int i=;i<=m;i++)mn[i]=,mx[i]=n;
int num=;
for(int i=,x,y;i<=n*m;i++)
{
x=(ps[i]-)/m+; y=(ps[i]-)%m+;
if(mn[y]>x||mx[y]<x)continue;
printf("%d ",i); num++;
if(num==n+m-)break;
for(int i=;i<y;i++)mx[i]=mnn(mx[i],x);
for(int i=y+;i<=m;i++)mn[i]=mxx(mn[i],x);
}
puts("");
return ;
}

最新文章

  1. ABP中使用Redis Cache(2)
  2. linux命令**50
  3. 关于tableView的优化
  4. 设计模式之工厂模式(Factory)
  5. Golang学习 - bufio 包
  6. Project Euler 86:Cuboid route 长方体路径
  7. BNUOJ-26586 Simon the Spider 最小生成树+枚举
  8. OC中-方法到底是如何使用的?
  9. codeforce 651B Beautiful Paintings
  10. OpenOffice 服务开机启动
  11. .NET 中易混淆的概念(Delegate vs Event)
  12. HDU 5811 Colosseo
  13. motan负载均衡/zookeeper集群/zookeeper负载均衡的关系
  14. (五)SpringBoot2.0基础篇- Mybatis与插件生成代码
  15. SQL Server 创建索引
  16. Python3自定义日志类教程
  17. 纯CSS3实现打火机火焰动画
  18. Fiddler 抓包https配置 提示:creation of the root certificate was not successful 证书安装不成功
  19. oracle数据类型表
  20. git关于 LF 与 CRLF

热门文章

  1. 【译】前端开发者都应知道的 jQuery 小技巧
  2. 洛谷 2233 [HNOI2002]公交车路线
  3. threading.local的作用?
  4. 超轻量级、高性能C日志库--EasyLogger
  5. 数据库存储I/O类型分析与配置
  6. WebApp页面开发小结
  7. J2EE SSH框架整合教程
  8. 视图的创建与使用 Sql Server View
  9. Data Structure Graph: prim
  10. ubuntu配置jdk环境