学习记录8.22 各种思维题+扫描线

思维题+扫描线"/>

学习记录8.22 各种思维题+扫描线

牛客多校第10场 I

题意：给定两个数组，从第一个数组和第二个数组中分别跳出一对数，要求这两对数做差的绝对值相等，如果有则输出下标，否则输出no

思路：当我们的数组没有重复的数字时，如果想要任意两个数的差值（在1e7之内）不同，经过打表发现数字约有4000个就可以达到，题目中给出数据范围是1e6个在1e7之内的数。所以去重之后可以在约为4000*4000的复杂度下求出答案。

1.我们对于a数组显然有去重的操作，我们设置一个数组记录每个数的最后一次出现的下标即可，特别注意的是两数差值为0的时候需要特殊记录一下。
2.我们对于第二个数组在输入的过程中，先检测是否b数组输入过这个数，如果是而且a数组也有差值为0的一对数，那么就找到了。否则：记录下来当前输入值和所有去重后a数组的值进行做差，开设nx和ny数组分别记录下产生这个差值的a数组中数的坐标和b数组中数的坐标，一旦再次出现这个数值立刻就可以匹配。
3.如果上述均失配，可以保证复杂度不过超过4000*4000（因为比这个数多的话一定就有匹配上的了），那么就可以输出-1了。

Yet Another FFT Problem?

#include<bits/stdc++.h>const int N = 2e7+100;int n,a[N],b,m;
int n1,A[N];
int nx[N],ny[N],u=1e7;
int vis[N],ggx=0,ggy;
bool ok=0;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);if(vis[a[i]]) {ggx=vis[a[i]];ggy=i;} elseA[++n1]=i;vis[a[i]]=i;}memset(vis,0,sizeof vis);for(int i=1;i<=m;i++) {scanf("%d",&b);if(vis[b]) {if(ggx) {printf("%d %d %d %d\n",ggx,ggy,vis[b],i);ok=1;break;}continue;}vis[b]=i;for(int j=1;j<=n1;j++) {int o=b-a[A[j]]+u;if(nx[o]) {printf("%d %d %d %d\n",nx[o],A[j],ny[o],i);ok=1;break;}nx[o]=A[j];ny[o]=i;}if(ok) break;}if(!ok) puts("-1");
}

话说这题居然又人用fft写了1800行，压着2900ms过了，太恐怖了。

C. Monoblock

题意：给定一个数组，设定一个区间的价值是此区间连续相同数块的个数。我们给出m次修改，每次将i位置的数值修改为x，每次修改完求整个数组全部区间的价值和。

思路：这个题非常邪恶。我们把贡献分成两份来计算是比较可行的方案。我们考虑分为对左边和对右边贡献来看。
例如 1 2 2 4 5的第3个数2
对左边：[1,3],[2,3],[3,3]显然都是产生了一个贡献。

对右边：[1,4][1,5][2,4][2,5][3,4][3,5]显然，当且仅当第i项和第i+1项不同时，第i项能够产生i*(n-i)的价值：也就是从1到i的数作为左端点和从i+1到n的数作为右端点可以让i点产生的价值。

而恰好，对右边的贡献是变化的，对左边的贡献不变，适合作为突破点。

这题的贡献分割特别邪恶，非常不好想，，，害。

#include <bits/stdc++.h>
using namespace std;#define int long longsigned main() 
{int n, m;cin >> n >> m;vector<int> a(n + 2, 0);for (int i = 1; i <= n; ++i) {cin >> a[i];}int ans = 0;for (int i = 1; i <= n; ++i) {ans += (a[i] != a[i + 1]) * (n - (i + 1) + 1) * i;}while (m--) {int i, x;cin >> i >> x;ans -= (a[i] != a[i - 1]) * (n - i + 1) * (i - 1);ans -= (a[i + 1] != a[i]) * (n - (i + 1) + 1) * i;a[i] = x;ans += (a[i] != a[i - 1]) * (n - i + 1) * (i - 1);ans += (a[i + 1] != a[i]) * (n - (i + 1) + 1) * i;cout << ans + n * (n + 1) / 2 << '\n';}
}

D. 2+ doors
这场感觉真的C>D

题意：构造一个长度为n的数组，要求如下：
1.m次规定，每次规定第i个数和第j个数做或运算等于x
2.求出的数组可能有多个，输出字典序最小的一个。

思路：每次规定直接给出了第i个数和第j个数那些位置可能为1，那么我们就全部都弄上1，预处理完了m次要求之后就大概能够筛选出各个位置的数那些位置可能为1.

第二步，赋值，格外注意类似于第x个数和第x个数或等于y这样的，这个就是直接确定数值了。

第三部，尽可能让各个二进制位的1往后移动，这样可以确保字典序最小。怎么移动？假设有好多好多数和x位置的数做了或，那么目前x位置留有的1都可以转移到这些数上，也就是说，求出这些数（包含x）共同的二进制位然后让x去掉这些二进制位分给后人承担即可，反正或运算，一个人有大家都有了。

#include <bits/stdc++.h>using namespace std;
#define int long long
const int N = 1e5+100;
vector<pair<int,int>> v[N];
int ans[N];
int fix[N];
signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int n,q,a,b,x;cin>>n>>q;for(int i=1;i<=n;i++){ans[i]=1<<30;ans[i]--;//2的 30次幂-1}for(int i=0;i<q;i++){cin>>a>>b>>x;//a位置和b位置异或得xv[a].push_back({b,x});//注册a位置与b异或得xv[b].push_back({a,x});//注册b位置与a异或得xans[a]&=x;//a位置与x做且ans[b]&=x;//a位置与x做且if(a==b)//显然就能确定a位置的数值了fix[a]=x;}for(int i=1;i<=n;i++){if(v[i].empty())//不被任何条件的限制，选择最小的数0ans[i]=0;if(fix[i])//既定值赋值ans[i]=fix[i];}for(int i=1;i<=n;i++)//贪心，让必须有的1尽可能的往后排{int an=(1<<30)-1;for(auto x:v[i]){an&=ans[x.first];}if(!fix[i])ans[i]-=an&ans[i];cout<<ans[i]<<' ';}
}

扫描线

P5490 【模板】扫描线

题意：有n个矩形罗列排放，求出这些矩形的并集面积。（这些矩形不会有斜着放的。）

扫描线，顾名思义，就是有个像是线段一样的东西从下到上去扫描整个图形，在扫描的过程中，我们会不断的碰到边
按照这个算法来，我们需要利用线段树来维护长度的变化，维护的方式是用的离散化，线段树每个点管辖的不是实际长度，而是对应的存储左右端点的数组。
比如x点的长度在线段树中是tree[x].l 和tree[x].r那么实际上还得转化到X[tree[x].l],X[tree[x].r],对应长度也就是X[tree[x].r]-X[tree[x].l]

注意点：
这里的x数组是对应的横坐标，主要用来计算横截线，但是当去重后用来bulid线段树之后，tree[X].l-tree[X].r对应的是X点代表的x[l]到x[r-1],所以使用的时候要对应的要搞r+1

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
using namespace std;
const int N = 1e6+100;
struct Line
{int l,r,h,mark;
};
bool cmp(const Line &a,const Line &b)
{return a.h<b.h;
}
struct segtree
{int l,r,len,sum;
};
int x[N<<1];
Line line[N<<1];
segtree tree[N<<2];
void bulid(int p,int l,int r)
{tree[p].l=l;tree[p].r=r;tree[p].len=0,tree[p].sum=0;if(l==r)return ;bulid(ls,l,mid);bulid(rs,mid+1,r);return ;
}
void up(int p)
{int l=tree[p].l,r=tree[p].r;if(tree[p].sum)tree[p].len=x[r+1]-x[l];elsetree[p].len=tree[ls].len+tree[rs].len;
}
void fixed(int p,int nl,int nr,int c)
{int l=tree[p].l,r=tree[p].r;if(x[r+1]<=nl||nr<=x[l])return ;if(nl<=x[l]&&x[r+1]<=nr){tree[p].sum+=c;up(p);return ;}if(x[mid]>=nl)fixed(ls,nl,nr,c);if(x[mid]<nr)fixed(rs,nl,nr,c);up(p);
}
signed main()
{int n,x1,y1,x2,y2;cin>>n;for(int i=1;i<=n;i++){cin>>x1>>y1>>x2>>y2;x[i*2-1]=x1;x[i*2]=x2;line[i*2-1]=(Line){x1,x2,y1,1};line[i*2]=(Line){x1,x2,y2,-1};}n<<=1;sort(x+1,x+n+1);sort(line+1,line+n+1,cmp);int tot=unique(x+1,x+n+1)-(x+1);bulid(1,1,tot-1);int ans=0;for(int i=1;i<n;i++){fixed(1,line[i].l,line[i].r,line[i].mark);ans+=tree[1].len*(line[i+1].h-line[i].h);}cout<<ans<<endl;return 0;
}

还有一道是变型情况，同样是给定点之后求出他们的周长并

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define lson (x << 1)
#define rson (x << 1 | 1)
using namespace std;
const int MAXN = 2e4;
int n, X[MAXN << 1];
int x1, y1, x2, y2, pre = 0; /* 先初始化为 0 */struct ScanLine {int l, r, h, mark;if(h == rhs.h)return mark > rhs.mark;return h < rhs.h;
//		注意！这里是后来被 hack 掉以后加上去的
//		在此感谢 @leprechaun_kdl 指出问题
//		如果出现了两条高度相同的扫描线，也就是两矩形相邻
//		那么需要先扫底边再扫顶边，否则就会多算这条边
//		这个对面积并无影响但对周长并有影响
//		hack 数据：2 0 0 4 4 0 4 4 8 输出应为：24
} line[MAXN];struct SegTree {int l, r, sum, len, c;
//  c表示区间线段条数bool lc, rc;
//  lc, rc分别表示左、右端点是否被覆盖
//  统计线段条数(tree[x].c)会用到
} tree[MAXN << 2];void build_tree(int x, int l, int r) {tree[x].l = l, tree[x].r = r;tree[x].lc = tree[x].rc = false;tree[x].sum = tree[x].len = 0;tree[x].c = 0;if(l == r)return;int mid = (l + r) >> 1;build_tree(lson, l, mid);build_tree(rson, mid + 1, r);
}void pushup(int x) {int l = tree[x].l, r = tree[x].r;if(tree[x].sum) {tree[x].len = X[r + 1] - X[l];tree[x].lc = tree[x].rc = true;tree[x].c = 1;
//      做好相应的标记}else {tree[x].len = tree[lson].len + tree[rson].len;tree[x].lc = tree[lson].lc, tree[x].rc = tree[rson].rc;tree[x].c = tree[lson].c + tree[rson].c;
//      如果左儿子左端点被覆盖，那么自己的左端点也肯定被覆盖；右儿子同理if(tree[lson].rc && tree[rson].lc)tree[x].c -= 1;
//      如果做儿子右端点和右儿子左端点都被覆盖，
//      那么中间就是连续的一段，所以要 -= 1}
}void edit_tree(int x, int L, int R, int c) {int l = tree[x].l, r = tree[x].r;if(X[l] >= R || X[r + 1] <= L)return;if(L <= X[l] && X[r + 1] <= R) {tree[x].sum += c;pushup(x);return;}edit_tree(lson, L, R, c);edit_tree(rson, L, R, c);pushup(x);
}ScanLine make_line(int l, int r, int h, int mark) {ScanLine res;res.l = l, res.r = r,res.h = h, res.mark = mark;return res;
}
//  POJ 不这样做就会CE，很难受int main() {scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%d %d %d %d", &x1, &y1, &x2, &y2);line[i * 2 - 1] = make_line(x1, x2, y1, 1);line[i * 2] = make_line(x1, x2, y2, -1);X[i * 2 - 1] = x1, X[i * 2] = x2;}n <<= 1;sort(line + 1, line + n + 1);sort(X + 1, X + n + 1);int tot = unique(X + 1, X + n + 1) - X - 1;build_tree(1, 1, tot - 1);int res = 0;for(int i = 1; i < n; i++) {edit_tree(1, line[i].l, line[i].r, line[i].mark);res += abs(pre - tree[1].len);pre = tree[1].len;
//      统计横边res += 2 * tree[1].c * (line[i + 1].h - line[i].h);
//      统计纵边}res += line[n].r - line[n].l;
//  特判一下枚举不到的最后一条扫描线printf("%d", res);return 0;
}