技巧总结
离散化:
void lsh(int *val)
{
unordered_map<int,int> mp;
int a[40005]={},tot=0;
for(int i=1;i<=n;i++) a[i]=*(val+i);
sort(a+1,a+1+n);
a[0]=-1;
for(int i=1;i<=n;i++)
if(a[i]!=a[i-1]) mp[a[i]]=++tot;
for(int i=1;i<=n;i++) *(val+i)=mp[*(val+i)];
}快读：
取消输入输出缓存
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);普通快读：
inline int read()
{
int x=0,c=getchar(),f=0;
for(;c>'9'||c<'0';f=c=='-',c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
inline void write(int x)
{
x<0?(putchar('-'),x=-x):1;
if(x>9) write(x/10);
putchar(x%10+'0');
}快到起飞！！！
#define getchar() \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt) \
? EOF \
: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
inline void write(int x)
{
if(x<0)x=(~x+1),putchar('-');
if(x>9)write(x/10);
putchar(x%10+'0');
}namespace IN{//快读
const int MAX_INPUT = 1000000;
#define getc() (p1==p2&&(p2=(p1=buf)+inbuf->sgetn(buf,MAX_INPUT),p1==p2)?EOF:*p1++)
char buf[MAX_INPUT],*p1,*p2;
template<typename T>inline bool read(T &x) {
static std::streambuf *inbuf=cin.rdbuf();
x=0;
register int f=0,flag=false;
register char ch=getc();
while(!isdigit(ch)){
if (ch=='-') f=1;
ch=getc();
}
if(isdigit(ch)) x=x*10+ch-'0',ch=getc(),flag=true;
while(isdigit(ch)) {
x=x*10+ch-48;
ch=getc();
}
x=f?-x:x;
return flag;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args) {
return read(a)&&read(args...);
}
#undef getc
}
namespace OUT{//快写
template<typename T>inline void put(T x){
static std::streambuf *outbuf=cout.rdbuf();
static char stack[21];
static int top=0;
if(x<0){
outbuf->sputc('-');
x=-x;
}
if(!x){
outbuf->sputc('0');
outbuf->sputc('\n');
return;
}
while(x){
stack[++top]=x%10+'0';
x/=10;
}
while(top){
outbuf->sputc(stack[top]);
--top;
}
outbuf->sputc('\n');
}
inline void putc(const char ch){
static std::streambuf *outbuf=cout.rdbuf();
outbuf->sputc(ch);
}
inline void putstr(string s){
for(register int i=0;i<s.length();i++) putc(s[i]);
}
template<typename T>inline void put(const char ch,T x){
static std::streambuf *outbuf=cout.rdbuf();
static char stack[21];
static int top = 0;
if(x<0){
outbuf->sputc('-');
x=-x;
}
if(!x){
outbuf->sputc('0');
outbuf->sputc(ch);
return;
}
while(x){
stack[++top]=x%10+'0';
x/=10;
}
while(top){
outbuf->sputc(stack[top]);
--top;
}
outbuf->sputc(ch);
}
template<typename T,typename ...Args> inline void put(T a,Args ...args){
put(a);put(args...);
}
template<typename T,typename ...Args> inline void put(const char ch,T a,Args ...args){
put(ch,a);put(ch,args...);
}
}
using IN::read;
using OUT::put;
using OUT::putc;
using OUT::putstr;super:
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstdint>
#include <cstring>
#include <functional>
#include <limits>
#include <numeric>
#include <tuple>
#include <vector>
#ifndef __OY_LINUXIO__
#define __OY_LINUXIO__
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <string>
#include <vector>
#ifdef __unix__
#include <sys/mman.h>
#include <sys/stat.h>
#endif
#if __cpp_constexpr >= 201907L
#define CONSTEXPR20 constexpr
#define INLINE20 constexpr
#else
#define CONSTEXPR20
#define INLINE20 inline
#endif
#define cin OY::LinuxIO::InputHelper<>::get_instance()
#define cout OY::LinuxIO::OutputHelper::get_instance()
#define endl '\n'
#ifndef INPUT_FILE
#define INPUT_FILE "in.txt"
#endif
#ifndef OUTPUT_FILE
#define OUTPUT_FILE "out.txt"
#endif
namespace OY
{
namespace LinuxIO
{
static constexpr size_t INPUT_BUFFER_SIZE = 1 << 26, OUTPUT_BUFFER_SIZE = 1 << 20;
#ifdef OY_LOCAL
static constexpr char input_file[] = INPUT_FILE, output_file[] = OUTPUT_FILE;
#else
static constexpr char input_file[] = "", output_file[] = "";
#endif
template <typename U, size_t E>
struct TenPow
{
static constexpr U value = TenPow<U, E - 1>::value * 10;
};
template <typename U>
struct TenPow<U, 0>
{
static constexpr U value = 1;
};
struct InputPre
{
uint32_t m_data[0x10000];
CONSTEXPR20 InputPre()
{
std::fill(m_data, m_data + 0x10000, -1);
for (size_t i = 0, val = 0; i != 10; i++)
for (size_t j = 0; j != 10; j++)
m_data[0x3030 + i + (j << 8)] = val++;
}
};
struct OutputPre
{
uint32_t m_data[10000];
CONSTEXPR20 OutputPre()
{
uint32_t *c = m_data;
for (size_t i = 0; i != 10; i++)
for (size_t j = 0; j != 10; j++)
for (size_t k = 0; k != 10; k++)
for (size_t l = 0; l != 10; l++)
*c++ = i + (j << 8) + (k << 16) + (l << 24) + 0x30303030;
}
};
template <size_t MMAP_SIZE = 1 << 30>
struct InputHelper
{
static INLINE20 InputPre pre{};
char *m_p, *m_c, *m_end;
InputHelper(FILE *file = stdin)
{
#ifdef __unix__
struct stat _stat;
auto fd = fileno(file);
fstat(fd, &_stat);
m_c = m_p = (char *)mmap(nullptr, _stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
m_end = m_p + _stat.st_size;
#else
uint32_t size = fread(m_c = m_p = new char[INPUT_BUFFER_SIZE], 1, INPUT_BUFFER_SIZE, file);
m_end = m_p + size;
#endif
}
static InputHelper<MMAP_SIZE> &get_instance()
{
static InputHelper<MMAP_SIZE> s_obj(*input_file ? fopen(input_file, "rt") : stdin);
return s_obj;
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &x)
{
x = 0;
while (!isdigit(*m_c))
m_c++;
x = *m_c++ ^ '0';
while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)])
x = x * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
if (isdigit(*m_c))
x = x * 10 + (*m_c++ ^ '0');
return *this;
}
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &x)
{
typename std::make_unsigned<Tp>::type t{};
bool sign{};
while (!isdigit(*m_c))
sign = (*m_c++ == '-');
t = *m_c++ ^ '0';
while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)])
t = t * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
if (isdigit(*m_c))
t = t * 10 + (*m_c++ ^ '0');
x = sign ? -t : t;
return *this;
}
InputHelper &operator>>(char &x)
{
while (*m_c <= ' ')
m_c++;
x = *m_c++;
return *this;
}
InputHelper &operator>>(std::string &x)
{
while (*m_c <= ' ')
m_c++;
char *c = m_c;
while (*c > ' ')
c++;
x.assign(m_c, c - m_c), m_c = c;
return *this;
}
InputHelper &operator>>(std::string_view &x)
{
while (*m_c <= ' ')
m_c++;
char *c = m_c;
while (*c > ' ')
c++;
x = std::string_view(m_c, c - m_c), m_c = c;
return *this;
}
};
struct OutputHelper
{
static INLINE20 OutputPre pre{};
FILE *m_file;
char m_p[OUTPUT_BUFFER_SIZE], *m_c, *m_end;
OutputHelper(FILE *file = stdout)
{
m_file = file;
m_c = m_p, m_end = m_p + OUTPUT_BUFFER_SIZE;
}
~OutputHelper() { flush(); }
static OutputHelper &get_instance()
{
static OutputHelper s_obj(*output_file ? fopen(output_file, "wt") : stdout);
return s_obj;
}
void flush() { fwrite(m_p, 1, m_c - m_p, m_file), m_c = m_p; }
OutputHelper &operator<<(char x)
{
if (m_end - m_c < 20)
flush();
*m_c++ = x;
return *this;
}
OutputHelper &operator<<(std::string_view s)
{
if (m_end - m_c < s.size())
flush();
memcpy(m_c, s.data(), s.size()), m_c += s.size();
return *this;
}
OutputHelper &operator<<(uint64_t x)
{
if (m_end - m_c < 20)
flush();
#define CASEW(w) \
case TenPow<uint64_t, w - 1>::value... TenPow<uint64_t, w>::value - 1: \
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, w - 4>::value]; \
m_c += 4, x %= TenPow<uint64_t, w - 4>::value;
switch (x)
{
CASEW(19);
CASEW(15);
CASEW(11);
CASEW(7);
case 100 ... 999:
*(uint32_t *)m_c = pre.m_data[x * 10];
m_c += 3;
break;
CASEW(18);
CASEW(14);
CASEW(10);
CASEW(6);
case 10 ... 99:
*(uint32_t *)m_c = pre.m_data[x * 100];
m_c += 2;
break;
CASEW(17);
CASEW(13);
CASEW(9);
CASEW(5);
case 0 ... 9:
*m_c++ = '0' + x;
break;
default:
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, 16>::value];
m_c += 4;
x %= TenPow<uint64_t, 16>::value;
CASEW(16);
CASEW(12);
CASEW(8);
case 1000 ... 9999:
*(uint32_t *)m_c = pre.m_data[x];
m_c += 4;
break;
}
#undef CASEW
return *this;
}
OutputHelper &operator<<(uint32_t x)
{
if (m_end - m_c < 20)
flush();
#define CASEW(w) \
case TenPow<uint32_t, w - 1>::value... TenPow<uint32_t, w>::value - 1: \
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, w - 4>::value]; \
m_c += 4, x %= TenPow<uint32_t, w - 4>::value;
switch (x)
{
default:
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, 6>::value];
m_c += 4;
x %= TenPow<uint32_t, 6>::value;
CASEW(6);
case 10 ... 99:
*(uint32_t *)m_c = pre.m_data[x * 100];
m_c += 2;
break;
CASEW(9);
CASEW(5);
case 0 ... 9:
*m_c++ = '0' + x;
break;
CASEW(8);
case 1000 ... 9999:
*(uint32_t *)m_c = pre.m_data[x];
m_c += 4;
break;
CASEW(7);
case 100 ... 999:
*(uint32_t *)m_c = pre.m_data[x * 10];
m_c += 3;
break;
}
#undef CASEW
return *this;
}
OutputHelper &operator<<(int64_t x)
{
if (x >= 0)
return (*this) << uint64_t(x);
else
return (*this) << '-' << uint64_t(-x);
}
OutputHelper &operator<<(int32_t x)
{
if (x >= 0)
return (*this) << uint32_t(x);
else
return (*this) << '-' << uint32_t(-x);
}
};
}
}
#endif
#ifndef __OY_FASTHEAP__
#define __OY_FASTHEAP__
namespace OY
{
namespace FHeap
{
using size_type = uint32_t;
template <typename Sequence>
struct Getter;
template <typename Tp>
struct Getter<std::vector<Tp>>
{
std::vector<Tp> &m_sequence;
Getter(std::vector<Tp> &sequence) : m_sequence(sequence) {}
const Tp &operator()(size_type index) const { return m_sequence[index]; }
};
template <typename Tp>
struct Getter<Tp *>
{
Tp *m_sequence;
Getter(Tp *sequence) : m_sequence(sequence) {}
const Tp &operator()(size_type index) const { return *(m_sequence + index); }
};
template <typename Mapping, typename Compare = std::less<void>>
class Heap
{
std::vector<size_type> m_heap, m_pos;
size_type m_size;
Mapping m_map;
Compare m_comp;
void _set(size_type x, size_type pos) { m_pos[m_heap[pos] = x] = pos; }
public:
Heap(size_type length, Mapping map, Compare comp = Compare()) : m_map(map), m_comp(comp) { resize(length); }
void resize(size_type length) { m_heap.resize(length * 2), m_pos.assign(length, -1), m_size = 0; }
void insert(size_type x)
{
_set(x, m_size * 2 + 1);
if (m_size)
{
_set(m_heap[m_size], m_size * 2);
auto &&cur_value = m_map(x);
for (size_type pos = m_size * 2; (pos >>= 1) && m_comp(m_map(m_heap[pos]), cur_value); m_heap[pos] = x)
{
}
}
m_size++;
}
void sift_up(size_type x)
{
auto &&cur_value = m_map(x);
size_type pos = m_pos[x];
while ((pos >>= 1) && (m_heap[pos] == x || m_comp(m_map(m_heap[pos]), cur_value)))
m_heap[pos] = x;
}
void sift_down(size_type x)
{
auto &&cur_value = m_map(x);
size_type pos = m_pos[x];
while ((pos >>= 1) && m_heap[pos] == x)
m_heap[pos] = std::max(m_heap[pos * 2], m_heap[pos * 2 + 1], [&](size_type x, size_type y)
{ return m_comp(m_map(x), m_map(y)); });
}
void clear()
{
std::fill_n(m_pos.data(), m_pos.size(), -1);
m_size = 0;
}
void push(size_type x) { contains(x) ? sift_up(x) : insert(x); }
size_type top() const { return m_heap[1]; }
void pop()
{
size_type x = m_heap[1], pos = m_pos[x];
m_pos[x] = -1;
if (--m_size)
{
if ((pos >> 1) == m_size)
_set(m_heap[pos ^ 1], m_size), pos = m_size;
else
_set(m_heap[m_size] == m_heap[m_size * 2] ? m_heap[m_size * 2 + 1] : m_heap[m_size * 2], pos), m_pos[m_heap[m_size]] = m_size;
while (pos >>= 1)
m_heap[pos] = std::max(m_heap[pos * 2], m_heap[pos * 2 + 1], [&](size_type x, size_type y)
{ return m_comp(m_map(x), m_map(y)); });
}
}
bool empty() const { return !m_size; }
size_type size() const { return m_size; }
bool contains(size_type x) const { return ~m_pos[x]; }
void check() const
{
if (empty())
return;
int L = m_size, R = m_size * 2 - 1, cnt = 0;
for (int i = 0; i < m_pos.size(); i++)
if (~m_pos[i])
{
if (!(L <= m_pos[i] and m_pos[i] <= R))
{
exit(1);
}
if (m_heap[m_pos[i]] != i)
{
exit(2);
}
cnt++;
}
if (cnt != m_size)
{
exit(3);
}
for (int i = m_size - 1; i; i--)
{
if (m_heap[i] != m_heap[i * 2] and m_heap[i] != m_heap[i * 2 + 1])
{
exit(4);
}
if (m_heap[i] == m_heap[i * 2])
{
if (m_comp(m_map(m_heap[i * 2]), m_map(m_heap[i * 2 + 1])))
{
exit(5);
}
}
if (m_heap[i] == m_heap[i * 2 + 1])
{
if (m_comp(m_map(m_heap[i * 2 + 1]), m_map(m_heap[i * 2])))
{
exit(6);
}
}
}
}
};
}
template <typename Tp, typename Compare = std::less<Tp>, typename HeapType = FHeap::Heap<FHeap::Getter<std::vector<Tp>>, Compare>>
auto make_FastHeap(FHeap::size_type length, std::vector<Tp> &items, Compare comp = Compare()) -> HeapType { return HeapType(length, FHeap::Getter<std::vector<Tp>>(items), comp); }
template <typename Tp, typename Compare = std::less<Tp>, typename HeapType = FHeap::Heap<FHeap::Getter<Tp *>, Compare>>
auto make_FastHeap(FHeap::size_type length, Tp *items, Compare comp = Compare()) -> HeapType { return HeapType(length, FHeap::Getter<Tp *>(items), comp); }
template <typename Mapping, typename Compare = std::less<void>>
using FastHeap = FHeap::Heap<Mapping, Compare>;
}
#endif卡常火车头：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")颜色封装函数
void Color(int a)//颜色封装函数
{
/*
* 0 — 白色
* 1 — 浅蓝
* 2 — 绿色
* 3 — 紫色
* 4 — 红色
* 5 — 黄色
* 6 — 深蓝
* 7 — 还原（浅灰）
* 8 — 深红
* 9 — 背景-浅蓝
* 10 — 背景-紫色
* 11 — 深紫
* 12 — 深黄
* 13 — 灰色
* 14 — 蓝绿
*/
if(a==0) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE); //白色
if(a==1) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN|FOREGROUND_BLUE); //浅蓝
if(a==2) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_GREEN); //绿色
if(a==3) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_BLUE); //紫色
if(a==4) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED); //红色
if(a==5) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|FOREGROUND_GREEN); //黄色
if(a==6) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_BLUE); //深蓝
if(a==7) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE); //还原（浅灰）
if(a==8) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED); //深红
if(a==9) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),BACKGROUND_INTENSITY|BACKGROUND_GREEN|BACKGROUND_BLUE); //背景-浅蓝
if(a==10) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),BACKGROUND_INTENSITY|BACKGROUND_RED|BACKGROUND_BLUE); //背景-紫色
if(a==11) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_BLUE); //深紫
if(a==12) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_GREEN); //深黄
if(a==13) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY); //灰色
if(a==14) SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_GREEN|FOREGROUND_BLUE); //蓝绿
}