闲话
duliu 题，写了 10k。
题意
形式化地，对于 \(1 \leq i \leq k\)，定义密码锁第 \(i\) 行的松散度为
\[c(i) = \max \limits _ {j = 1} ^ n a _ {i, j} - \min \limits _ {j = 1} ^ n a _ {i, j} \]同时定义整个密码锁的松散度为
\[C = \max \limits _ {1 \leq i \leq k} c(i) \]求拨动若干次后最小的 \(C\) 值。
第一类测试点共有十二个，保证 \(k \leq 3\)，\(n \leq 5 \times 10 ^ 4\)，\(\sum n \leq 1.5 \times 10 ^ 5\)。
第二类测试点共有八个，保证 \(k = 4\)，\(n \leq 10 ^ 4\)，
\(\sum n \leq 3 \times 10 ^ 4\)。
做法
对 \(k\) 的大小分类讨论。
\(k=1,2\) 做法显然，略。
\(k=3\)
思路：
\[\left\{ \begin{align*} & \text{dp} \\ & \text{转为二分判定} \\ & \text{模拟退火} \end{align*} \right. \]看起来转为二分判定比较靠谱。
二分时钦定最大值在第一行，枚举最小值在哪一行。
有最大值/最小值的行容易判断是否合法。对于剩下一行，问题转化为：数轴上多个带颜色的点，求是否有一个长度为（当前二分的答案）的区间覆盖每个颜色的点至少一个。
设目前二分的答案为 \(x\)，将每个点 \(i\) 替换为 \([i, i+x+1)\) 的区间，则这些区间的交即为上述问题区间的右端点。问题再次转化为：数轴上多个区间，求是否存在至少被 \(n\) 个区间覆盖的点。注意，对于同种颜色的点，区间要先取并。
区间覆盖即区间加，可以用差分维护。最后将差分数组做一个前缀和，途中顺便检查是否有点的值等于 \(n\) 即可。
时间复杂度 \(O((n+a) \log a)\)。
bool check3(int x, int mn, int mx, bool dmn){ // mx on first{{{
std::fill(delta, delta+A+1, 0); // 差分数组
static std::vector<std::pair<int, int>> segs(3); // 使用类珂树维护区间并
UP(i, 0, in){
bool valid = false;
segs.clear();
UP(j, 0, 3){
if(mx-ia[i][j] <= x && ia[i][(1+dmn+j)%3]-mn <= x){
valid = true;
int pl = ia[i][(1+!dmn+j)%3];
segs.push_back({ pl, std::min(A, pl+x+1) }); // [l, r)
}
}
if(!valid) return false;
std::sort(segs.begin(), segs.end());
for(auto k=segs.begin();;){
auto j = k; j++;
if(j == segs.end() || j->first > k->second){
delta[k->first]++;
delta[k->second]--;
if(j == segs.end()) break;
k = j;
} else {
k->second = j->second;
segs.erase(j);
}
}
}
if(delta[0] == in) return true;
UP(i, 1, A){
delta[i] += delta[i-1];
if(delta[i] == in) return true;
}
return false;
}/*}}}*/
\(k=4\)
与 \(k=3\) 类似，但区间交换成了矩形交。
问题是，二维差分数组的规模达到了 \(\Theta(n^2)\)，必定超时。
我会 KDT！对所有单点离线建树，跑 \(\Theta(n)\) 次查询矩阵和。
然而结果是 TLE。
考虑扫描线，用线段树维护动态的最值。
bool check4(int x, int mn, int mx, int dmn){ // mx on first{{{
static std::vector< std::tuple<int, int, int, int >> pts; // x, delta, yl, yr
static std::vector<std::tuple<int, int, int, int>> lines; // x, yl, yr, delta
static std::multiset<std::pair<int, int>> segs; // x, yl, yr, delta
pts.clear();
UP(i, 0, in){
bool valid = false;
lines.clear();
UP(j, 0, 4){
if(mx-ia[i][j] <= x && ia[i][(1+dmn+j)%4]-mn <= x){
valid = true;
int xx = ia[i][(1+(dmn+1)%3+j)%4],
yy = ia[i][(1+(dmn+2)%3+j)%4];
lines.push_back({ xx, yy, std::min(A, yy+x+1), 1 });
lines.push_back({ std::min(A, xx+x+1), yy, std::min(A, yy+x+1), -1 });
}
}
if(!valid) return false;
segs.clear();
std::sort(lines.begin(), lines.end());
int lastx = -1;
for(auto j:lines){
if(lastx != -1 && !segs.empty()){
int lasty = segs.begin()->first;
for(auto k=segs.begin(); ;){
auto add = [&](){
pts.push_back({lastx, 1, lasty, k->second});
pts.push_back({std::get<0>(j), -1, lasty, k->second});
};
auto l=k; l++;
if(l==segs.end() || l->first > k->second){
add();
lasty = l->first;
if(l == segs.end()) break;
k=l;
} else {
k=l;
}
}
}
if(std::get<3>(j) == -1){
segs.erase(segs.find({std::get<1>(j), std::get<2>(j)}));
} else {
segs.insert({std::get<1>(j), std::get<2>(j)});
}
lastx = std::get<0>(j);
}
}
std::sort(pts.begin(), pts.end());
segt::nodcnt = 0;
segt::Node *rt = segt::build(segt::nnod(), 0, A);
for(auto i:pts){
segt::add(rt, std::get<2>(i), std::get<3>(i), std::get<1>(i));
if(rt->mx == in) return true;
}
return false;
}/*}}}*/
然而这样做开了 -O3 仍然会在 LOJ 上 TLE 四个点，获得 80 pts 的好成绩。
注意到每次线段树的形态都是不变的，可以打 tag 标记线段树的清空。可以获得 100 pts 的好成绩。
时间复杂度 \(O(n \log^2 a)\)。
10 KiB 完整代码
#include <set>
#include <vector>
#include <iostream>
#include <functional>
#include <tuple>
#include <algorithm>
#define UP(i,s,e) for(auto i=s; i<e; ++i)
#define USE_SEGT 1
#define DEBUG_SEGT 0
namespace IO{
struct IOer{
IOer& operator>>(int& x){
x=0; static char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)){
x = x*10 + c-'0';
c = getchar();
}
return *this;
}
IOer& operator<<(int x){
printf("%d", x);
return *this;
}
IOer& operator<<(char x){
putchar(x);
return *this;
}
};
}
IO::IOer cin, cout;
//using std::cin; using std::cout;
constexpr int N = 5e4, A = 3e4+1;
namespace KDT{ // }{{{
constexpr int SIZ = 24*N;
struct Point{
int x, y, delta;
bool operator<(Point b){
if(x != b.x) return x < b.x;
return y < b.y;
}
};
bool cmpx(Point a, Point b){ return a.x < b.x; }
bool cmpy(Point a, Point b){ return a.y < b.y; }
std::function<bool(Point, Point)> cmps[] = {cmpx, cmpy};
struct Node{
Node *ls, *rs;
int xl, xr, yl, yr, sum;
} nil_, *nil=&nil_, nds[SIZ];
int nodcnt=0;
Node *nnod(){ return nds+nodcnt++; }
void upd(Node *rt){
if(rt->ls == nil) return;
rt->xl = std::min(rt->ls->xl, rt->rs->xl);
rt->xr = std::max(rt->ls->xr, rt->rs->xr);
rt->yl = std::min(rt->ls->yl, rt->rs->yl);
rt->yr = std::max(rt->ls->yr, rt->rs->yr);
rt->sum = rt->ls->sum + rt->rs->sum;
}
Node *build(Node *rt, int l, int r, Point *data, int dim=0){
if(l == r-1){
rt->xl = data[l].x;
rt->yl = data[l].y;
rt->sum = data[l].delta;
rt->xr = rt->xl+1;
rt->yr = rt->yl+1;
rt->ls = rt->rs = nil;
return rt;
}
int mid = (l+r)/2;
std::nth_element(data+l, data+mid, data+r, cmps[dim]);
rt->ls = build(nnod(), l, mid, data, dim^1);
rt->rs = build(nnod(), mid, r, data, dim^1);
upd(rt);
return rt;
}
int querysum(Node *rt, int xl, int xr, int yl, int yr){
if(rt->xl >= xr || rt->xr <= xl || rt->yl >= yr || rt->yr <= yl){
return 0;
}
if(rt->xl >= xl && rt->xr <= xr && rt->yl >= yl && rt->yr <= yr){
return rt->sum;
}
return querysum(rt->ls, xl, xr, yl, yr) +
querysum(rt->rs, xl, xr, yl, yr);
}
} // {}}}
namespace segt{ // }{{{
constexpr int SIZ = A*2;
struct Node{
Node *ls, *rs;
int l, r;
int lazy;
int mx;
bool cleartag;
} nil_, *nil=&nil_, nds[SIZ];
int nodcnt = 0;
Node *nnod(){ return nds+nodcnt++; }
void upd(Node *rt){
if(rt->ls == nil){
rt->mx = rt->lazy;
return;
}
rt->mx = std::max(rt->ls->mx, rt->rs->mx) + rt->lazy;
}
void pushd(Node *rt){
if(!rt->cleartag) return;
rt->cleartag = false;
rt->lazy = rt->mx = 0;
if(rt->ls == nil) return;
rt->ls->cleartag = rt->rs->cleartag = true;
rt->ls->mx = rt->rs->mx = 0;
}
Node *build(Node *rt, int l, int r){
rt->l = l; rt->r = r;
rt->lazy = rt->mx = 0;
if(l == r-1){
rt->ls = rt->rs = nil;
return rt;
}
int mid = (l+r)/2;
rt->ls = build(nnod(), l, mid);
rt->rs = build(nnod(), mid, r);
return rt;
}
void add(Node *rt, int l, int r, int delta){
if(rt->r <= l || rt->l >= r) return;
pushd(rt);
if(rt->l >= l && rt->r <= r){
rt->lazy += delta;
upd(rt);
return;
}
add(rt->ls, l, r, delta);
add(rt->rs, l, r, delta);
upd(rt);
}
} // {}}}
namespace m{ // }{{{
int ia[N][4], in;
int delta[A+1];
void init(int k){
cin >> in;
UP(j, 0, k) UP(i, 0, in){
cin >> ia[i][j];
}
}
int calcc(int k){
int mn = ia[0][k], mx = ia[0][k];
UP(i, 0, in){
mn = std::min(mn, ia[i][k]);
mx = std::max(mx, ia[i][k]);
}
return mx-mn;
}
bool check3(int x, int mn, int mx, bool dmn){ // mx on first{{{
std::fill(delta, delta+A+1, 0);
static std::vector<std::pair<int, int>> segs(3);
UP(i, 0, in){
bool valid = false;
segs.clear();
UP(j, 0, 3){
if(mx-ia[i][j] <= x && ia[i][(1+dmn+j)%3]-mn <= x){
valid = true;
int pl = ia[i][(1+!dmn+j)%3];
segs.push_back({ pl, std::min(A, pl+x+1) }); // [l, r)
//delta[ia[i][(1+!dmn+j)%3]] += 1;
//delta[std::min(in, ia[i][(1+!dmn+j)%3]+x+1)] -= 1;
}
}
if(!valid) return false;
std::sort(segs.begin(), segs.end());
for(auto k=segs.begin();;){
auto j = k; j++;
if(j == segs.end() || j->first > k->second){
delta[k->first]++;
delta[k->second]--;
if(j == segs.end()) break;
k = j;
} else {
k->second = j->second;
segs.erase(j);
}
}
}
if(delta[0] == in) return true;
UP(i, 1, A){
delta[i] += delta[i-1];
if(delta[i] == in) return true;
}
return false;
}/*}}}*/
bool check4(int x, int mn, int mx, int dmn){ // mx on first{{{
#if USE_SEGT
static std::vector<
std::tuple<int, int, int, int
#if DEBUG_SEGT
, int
#endif
>> pts; // x, delta, yl, yr
#else
static std::vector<KDT::Point> pts; // x, y, delta
#endif
static std::vector<std::tuple<int, int, int, int>> lines; // x, yl, yr, delta
static std::multiset<std::pair<int, int>> segs;
// x, yl, yr, delta
pts.clear();
UP(i, 0, in){
bool valid = false;
lines.clear();
UP(j, 0, 4){
if(mx-ia[i][j] <= x && ia[i][(1+dmn+j)%4]-mn <= x){
valid = true;
int xx = ia[i][(1+(dmn+1)%3+j)%4],
yy = ia[i][(1+(dmn+2)%3+j)%4];
lines.push_back({
xx,
yy,
std::min(A, yy+x+1),
1
});
lines.push_back({
std::min(A, xx+x+1),
yy,
std::min(A, yy+x+1),
-1
});
}
}
if(!valid) return false;
segs.clear();
std::sort(lines.begin(), lines.end());
int lastx = -1;
for(auto j:lines){
if(lastx != -1 && !segs.empty()){
int lasty = segs.begin()->first;
for(auto k=segs.begin(); ;){
auto add = [&](){
#if USE_SEGT
#if DEBUG_SEGT
pts.push_back({lastx, 1, lasty, k->second, i});
pts.push_back({std::get<0>(j), -1, lasty, k->second, i});
#else
pts.push_back({lastx, 1, lasty, k->second});
pts.push_back({std::get<0>(j), -1, lasty, k->second});
#endif
#else
pts.push_back({lastx, lasty, 1});
pts.push_back({lastx, k->second, -1});
pts.push_back({std::get<0>(j), lasty, -1});
pts.push_back({std::get<0>(j), k->second, 1});
#endif
};
auto l=k; l++;
if(l==segs.end() || l->first > k->second){
add();
lasty = l->first;
if(l == segs.end()) break;
k=l;
} else {
k=l;
}
}
}
if(std::get<3>(j) == -1){
segs.erase(segs.find({std::get<1>(j), std::get<2>(j)}));
} else {
segs.insert({std::get<1>(j), std::get<2>(j)});
}
lastx = std::get<0>(j);
}
}
std::sort(pts.begin(), pts.end());
#if USE_SEGT
// segt::nodcnt = 0;
static segt::Node *rt = segt::build(segt::nnod(), 0, A);
rt->cleartag = true;
for(auto i:pts){
segt::add(rt, std::get<2>(i), std::get<3>(i), std::get<1>(i));
if(rt->mx == in) return true;
}
#else
for(auto i=pts.begin(); ; ){
auto j=i; j++;
if(j == pts.end()) break;
if(i->x == j->x && i->y == j->y){
i->delta += j->delta;
pts.erase(j);
} else {
if(i->delta == 0) pts.erase(i);
i=j;
}
}
KDT::nodcnt = 0;
KDT::Node *rt = KDT::build(KDT::nnod(), 0, pts.size(), pts.data());
for(auto i:pts){
if(KDT::querysum(rt, 0, i.x+1, 0, i.y+1) == in) return true;
}
#endif
return false;
}/*}}}*/
void work1(){ init(1); cout << calcc(0) << '\n'; }
void work2(){ init(2); UP(i, 0, in){ if(ia[i][0] > ia[i][1]) std::swap(ia[i][0], ia[i][1]); } cout << std::max(calcc(0), calcc(1)) << '\n'; }
void work3(){
init(3);
int mx=ia[0][0], mn=ia[0][0];
UP(i, 0, in) UP(j, 0, 3){
mx = std::max(mx, ia[i][j]);
mn = std::min(mn, ia[i][j]);
}
int l=-1, r=mx-mn+0; // (l, r]
while(r-l>1){
int mid=(l+r)/2;
if(check3(mid, mn, mx, true) || check3(mid, mn, mx, false)){
r=mid;
} else l=mid;
}
cout << r << '\n';
}
void work4(){
init(4);
int mx=ia[0][0], mn=ia[0][0];
UP(i, 0, in) UP(j, 0, 4){
mx = std::max(mx, ia[i][j]);
mn = std::min(mn, ia[i][j]);
}
int l=-1, r=mx-mn+0; // (l, r]
while(r-l>1){
//int mid= (r-l) > 100 ? r-(r-l)/4 : (l+r)/2;
int mid = (l+r)/2;
if(check4(mid, mn, mx, 0) || check4(mid, mn, mx, 1) || check4(mid, mn, mx, 2)){
r=mid;
} else l=mid;
}
cout << r << '\n';
}
} // {}}}
using namespace m;
int main(){
int it, ik;
cin >> it >> ik;
UP(i, 0, it){
if(ik == 1) work1();
else if(ik == 2) work2();
else if(ik == 3) work3();
else work4();
}
return 0;
}