新代码o2 91pts, ofast61pts....难受
```cpp
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
namespace IO{ inline char nc() { static char buf[2000000], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 2000000, stdin), p1 == p2) ? EOF : *p1++; } inline ll read() { char ch = nc(); ll tf = 0; ll sum = 0; while((ch < '0' || ch > '9') && (ch != '-')) ch = nc(); tf = ((ch == '-') && (ch = nc())); while(ch >= '0' && ch <= '9') sum = sum * 10+ (ch - 48), ch = nc(); (tf) && (sum =- sum); return sum; }
}
const int N=50000+10;
const int M=N<<2;
const int P=N*17*17;
struct Node{ int lc,rc; ll sum,add; Node():lc(0),rc(0),sum(0LL),add(0LL){}
}t[P];int cnt;
struct Q{ int opt,l,r;ll c; Q(){} }q[N];
inline int newnode(){ return ++cnt; }
int n,m,maxn,b[N];
#define ls (o<<1)
#define rs ((o<<1)|1)
int L[M],R[M],tree[M];
void build(int o,int l,int r){ L[o]=l;R[o]=r;tree[o]=0; if(l==r) return ; int mid=(l+r)>>1; build(ls,l,mid);build(rs,mid+1,r);
}
inline int len(int l,int r){ return r-l+1; }
inline void pushdown(int o,int L,int R){ int mid=(L+R)>>1; t[t[o].lc].sum+=t[o].add*len(L,mid); t[t[o].lc].add+=t[o].add; t[t[o].rc].sum+=t[o].add*len(mid+1,R); t[t[o].rc].add+=t[o].add; t[o].add=0;
}
inline void pushup(int o){ t[o].sum=t[t[o].lc].sum+t[t[o].rc].sum; }
inline int intersect(int a,int b,int c,int d){ int x=max(a,c),y=min(b,d); if(x>y) return 0; return y-x+1;
}
void add(int o,int L,int R,int l,int r){ if(L>r||R<l) return ; if(l<=L&&R<=r){ t[o].add++; t[o].sum+=len(L,R); return ; } int mid=(L+R)>>1; if(t[o].lc==0) t[o].lc=newnode(); if(t[o].rc==0) t[o].rc=newnode(); pushdown(o,L,R); add(t[o].lc,L,mid,l,r); add(t[o].rc,mid+1,R,l,r); t[o].sum+=intersect(L,R,l,r);
}
ll query(int o,int L,int R,int l,int r){ if(o==0||L>r||R<l) return 0; if(l<=L&&R<=r) return t[o].sum; if(t[o].lc==0) t[o].lc=newnode(); if(t[o].rc==0) t[o].rc=newnode(); pushdown(o,L,R); int mid=(L+R)>>1; return query(t[o].lc,L,mid,l,r)+query(t[o].rc,mid+1,R,l,r);
}
void insert(int o,int l,int r,int c){ if(tree[o]==0) tree[o]=newnode(); add(tree[o],1,n,l,r); if(L[o]==R[o]) return ; int mid=(L[o]+R[o])>>1; if(c<=mid) insert(ls,l,r,c); else insert(rs,l,r,c);
}
int kth(int o,int l,int r,ll k){ if(L[o]==R[o]) return L[o]; ll rcnt=query(tree[rs],1,n,l,r); if(rcnt>=k) return kth(rs,l,r,k); return kth(ls,l,r,k-rcnt);
}
inline int getid(int v){ int l=1,r=maxn,mid=0,ans=0; while(l<=r){ mid=(l+r)>>1; if(b[mid]<=v){ ans=mid; l=mid+1; }else r=mid-1; } return ans;
}
void init(){ sort(b+1,b+1+maxn); int i=1,j=1; while(j<=maxn){ b[i]=b[j]; while(b[i]==b[j]&&j<=maxn) ++j; ++i; }maxn=i-1; for(int k=0;k<m;++k) if(q[k].opt==1) q[k].c=getid(q[k].c);
}
void out(int x){ if(x<0){ out(-x); return ; } if(x<10){ putchar(x+'0'); return ; } out(x/10); putchar(x%10 +'0');
}
//inline void print(int x){ printf("%d\n",x); }
inline void print(int x){ out(x);putchar('\n'); }
int main(){ //freopen("in.in","r",stdin); using namespace IO; n=read();m=read(); for(register int i=0;i<m;++i){ q[i].opt=read(); q[i].l=read(); q[i].r=read(); q[i].c=read(); if(q[i].opt==1) b[++maxn]=q[i].c; } init(); build(1,1,maxn); for(register int i=0;i<m;++i){ if(q[i].opt==1) insert(1,q[i].l,q[i].r,q[i].c); else print(b[kth(1,q[i].l,q[i].r,q[i].c)]); } return 0;
}
```
by hehelego @ 2018-12-05 06:49:09
qaq回去上课前再来求一波常数优化QAQ...就差输出优化没加了吧....晚上试试标记永久化?
目前代码这样.换掉了几个不必要的long long.
```cpp
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
namespace IO{
inline char nc() {
static char buf[2000000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 2000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline ll read() {
char ch = nc();
ll tf = 0;
ll sum = 0;
while((ch < '0' || ch > '9') && (ch != '-')) ch = nc();
tf = ((ch == '-') && (ch = nc()));
while(ch >= '0' && ch <= '9') sum = sum * 10+ (ch - 48), ch = nc();
(tf) && (sum =- sum);
return sum;
}
}
const int N=50000+10;
const int M=N<<2;
const int P=N*17*17;
struct Node{
int lc,rc,add;
ll sum;
Node():lc(0),rc(0),add(0),sum(0LL){}
}t[P];int cnt;
struct Q{ int opt,l,r;ll c; Q(){} }q[N];
inline int newnode(){ return ++cnt; }
int n,m,maxn,b[N];
#define ls (o<<1)
#define rs ((o<<1)|1)
int L[M],R[M],tree[M];
void build(int o,int l,int r){
L[o]=l;R[o]=r;tree[o]=0;
if(l==r) return ;
int mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
}
inline int len(int l,int r){ return r-l+1; }
inline void pushdown(int o,int L,int R){
int mid=(L+R)>>1;
t[t[o].lc].sum+=1ll*t[o].add*len(L,mid);
t[t[o].lc].add+=t[o].add;
t[t[o].rc].sum+=1ll*t[o].add*len(mid+1,R);
t[t[o].rc].add+=t[o].add;
t[o].add=0;
}
inline void pushup(int o){ t[o].sum=t[t[o].lc].sum+t[t[o].rc].sum; }
inline int intersect(int a,int b,int c,int d){
int x=max(a,c),y=min(b,d);
if(x>y) return 0;
return y-x+1;
}
void add(int o,int L,int R,int l,int r){
if(L>r||R<l) return ;
if(l<=L&&R<=r){
t[o].add++;
t[o].sum+=1ll*len(L,R);
return ;
}
int mid=(L+R)>>1;
if(t[o].lc==0) t[o].lc=newnode();
if(t[o].rc==0) t[o].rc=newnode();
pushdown(o,L,R);
add(t[o].lc,L,mid,l,r);
add(t[o].rc,mid+1,R,l,r);
t[o].sum+=intersect(L,R,l,r);
}
ll query(int o,int L,int R,int l,int r){
if(o==0||L>r||R<l) return 0;
if(l<=L&&R<=r) return t[o].sum;
if(t[o].lc==0) t[o].lc=newnode();
if(t[o].rc==0) t[o].rc=newnode();
pushdown(o,L,R);
int mid=(L+R)>>1;
return query(t[o].lc,L,mid,l,r)+query(t[o].rc,mid+1,R,l,r);
}
void insert(int o,int l,int r,int c){
if(tree[o]==0) tree[o]=newnode();
add(tree[o],1,n,l,r);
if(L[o]==R[o]) return ;
int mid=(L[o]+R[o])>>1;
if(c<=mid) insert(ls,l,r,c);
else insert(rs,l,r,c);
}
int kth(int o,int l,int r,ll k){
if(L[o]==R[o]) return L[o];
ll rcnt=query(tree[rs],1,n,l,r);
if(rcnt>=k) return kth(rs,l,r,k);
return kth(ls,l,r,k-rcnt);
}
inline int getid(int v){
int l=1,r=maxn,mid=0,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(b[mid]<=v){
ans=mid;
l=mid+1;
}else r=mid-1;
}
return ans;
}
void init(){
sort(b+1,b+1+maxn);
int i=1,j=1;
while(j<=maxn){
b[i]=b[j];
while(b[i]==b[j]&&j<=maxn) ++j;
++i;
}maxn=i-1;
for(int k=0;k<m;++k)
if(q[k].opt==1) q[k].c=getid(q[k].c);
}
void out(int x){
if(x<0){ out(-x); return ; }
if(x<10){ putchar(x+'0'); return ; }
out(x/10); putchar(x%10 +'0');
}
//inline void print(int x){ printf("%d\n",x); }
inline void print(int x){ out(x);putchar('\n'); }
int main(){
//freopen("in.in","r",stdin);
using namespace IO;
n=read();m=read();
for(register int i=0;i<m;++i){
q[i].opt=read();
q[i].l=read();
q[i].r=read();
q[i].c=read();
if(q[i].opt==1) b[++maxn]=q[i].c;
}
init();
build(1,1,maxn);
for(register int i=0;i<m;++i){
if(q[i].opt==1) insert(1,q[i].l,q[i].r,q[i].c);
else print(b[kth(1,q[i].l,q[i].r,q[i].c)]);
}
return 0;
}
```
by hehelego @ 2018-12-05 12:33:26
感觉对于树套树卡得太紧了...评测机的性能波动都能+- 30pts....服了...窝什么时候能卡过去啊。
by hehelego @ 2018-12-05 12:34:18
经过惨无人道的优化之后变成了这样....只差以恶标记永久化还没用吧?或许还可以上zkw那种自底向上的玩法降低常数?
代码如下
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
namespace IO{
const int IN_LEN=10000000;
inline char nc() {
static char buf[IN_LEN], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, IN_LEN, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read() {
char ch = nc();
T tf = 0;
T sum = 0;
while((ch < '0' || ch > '9') && (ch != '-')) ch = nc();
tf = ((ch == '-') && (ch = nc()));
while(ch >= '0' && ch <= '9') sum = sum * 10+ (ch - 48), ch = nc();
(tf) && (sum =- sum);
return sum;
}
inline int gi(){ return read<int>(); }
inline ll gll(){ return read<ll>(); }
const int OUT_LEN=10000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}
inline void print(int x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) print((char)buf[cnt--]);
}
print('\n');
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
}
const int N=50000+10;
const int M=N<<2;
const int P=N*17*17;
struct Node{
uint lc,rc,add;
ll sum;
Node():lc(0),rc(0),add(0),sum(0LL){}
}t[P];uint cnt;
struct Q{ int opt,l,r;ll c; }q[N];
inline uint newnode(){ return ++cnt; }
uint n,m,maxn;
#define ls (o<<1)
#define rs ((o<<1)|1)
uint L[M],R[M],tree[M];
void build(uint o,uint l,uint r){
L[o]=l;R[o]=r;tree[o]=newnode();
if(l==r) return ;
uint mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
}
inline uint len(uint l,uint r){ return r-l+1; }
inline void pushdown(uint o,uint L,uint R){
uint mid=(L+R)>>1;
if(t[o].add==0) return ;
t[t[o].lc].sum+=1ll*t[o].add*len(L,mid);
t[t[o].lc].add+=t[o].add;
t[t[o].rc].sum+=1ll*t[o].add*len(mid+1,R);
t[t[o].rc].add+=t[o].add;
t[o].add=0;
}
inline uint intersect(uint a,uint b,uint c,uint d){
int x=max(a,c),y=min(b,d);
if(x>y) return 0;
return y-x+1;
}
void add(uint o,uint L,uint R,uint l,uint r){
if(L>r||R<l) return ;
t[o].sum+=intersect(L,R,l,r);
if(l<=L&&R<=r){ t[o].add++; return ; }
uint mid=(L+R)>>1;
if(t[o].lc==0) t[o].lc=newnode();
if(t[o].rc==0) t[o].rc=newnode();
pushdown(o,L,R);
add(t[o].lc,L,mid,l,r);
add(t[o].rc,mid+1,R,l,r);
}
ll query(uint o,uint L,uint R,uint l,uint r){
if(o==0||L>r||R<l) return 0;
if(l<=L&&R<=r) return t[o].sum;
if(t[o].lc==0) t[o].lc=newnode();
if(t[o].rc==0) t[o].rc=newnode();
pushdown(o,L,R);
uint mid=(L+R)>>1;
return query(t[o].lc,L,mid,l,r)+query(t[o].rc,mid+1,R,l,r);
}
void insert(uint o,uint l,uint r,uint c){
add(tree[o],1,n,l,r);
if(L[o]==R[o]) return ;
uint mid=(L[o]+R[o])>>1;
if(c<=mid) insert(ls,l,r,c);
else insert(rs,l,r,c);
}
uint kth(uint o,uint l,uint r,ll k){
if(L[o]==R[o]) return L[o];
ll rcnt=query(tree[rs],1,n,l,r);
if(rcnt>=k) return kth(rs,l,r,k);
return kth(ls,l,r,k-rcnt);
}
struct B{
int val,id;
inline bool operator<(const B &x)const{ return val<x.val; }
}b[N];
void init(){
sort(b+1,b+1+maxn);
uint i=1,j=1;
while(j<=maxn){
b[i]=b[j];
while(b[i].val==b[j].val&&j<=maxn) q[b[j++].id].c=i;
++i;
}maxn=i-1;
}
using namespace IO;
int main(){
//freopen("in.in","r",stdin);
//freopen("tmp","w",stdout);
n=gi();m=gi();
for(register uint i=0;i<m;++i){
q[i].opt=gi();
q[i].l=gi();
q[i].r=gi();
q[i].c=gll();
if(q[i].opt==1){ b[++maxn].val=q[i].c; b[maxn].id=i; }
}
init();
build(1,1,maxn);
for(register uint i=0;i<m;++i){
if(q[i].opt==1) insert(1,q[i].l,q[i].r,q[i].c);
else print(b[kth(1,q[i].l,q[i].r,q[i].c)].val);
}
flush();
return 0;
}
```
by hehelego @ 2018-12-05 17:27:53
btw,ofast好像LG上用不了啊....
求各位dalao帮juruo oier优化一波啊...已经卡三天了233.
by hehelego @ 2018-12-05 17:28:49
尝试树状数组套线段树？
by mrsrz @ 2018-12-05 17:40:45
标记永久化上了.直接AC...emm...
代码如下,晚上写题解先回去上课了2333
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
namespace IO{
const int IN_LEN=10000000;
inline char nc() {
static char buf[IN_LEN], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, IN_LEN, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read() {
char ch = nc();
T tf = 0;
T sum = 0;
while((ch < '0' || ch > '9') && (ch != '-')) ch = nc();
tf = ((ch == '-') && (ch = nc()));
while(ch >= '0' && ch <= '9') sum = sum * 10+ (ch - 48), ch = nc();
(tf) && (sum =- sum);
return sum;
}
inline int gi(){ return read<int>(); }
inline ll gll(){ return read<ll>(); }
const int OUT_LEN=10000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}
inline void print(int x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) print((char)buf[cnt--]);
}
print('\n');
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
}
const int N=50000+10;
const int M=N<<2;
const int P=N*17*17;
struct Node{
uint lc,rc,add;
ll sum;
Node():lc(0),rc(0),add(0),sum(0LL){}
}t[P];uint cnt;
struct Q{ int opt,l,r;ll c; }q[N];
inline uint newnode(){ return ++cnt; }
uint n,m,maxn;
#define ls (o<<1)
#define rs ((o<<1)|1)
uint L[M],R[M],tree[M];
void build(uint o,uint l,uint r){
L[o]=l;R[o]=r;tree[o]=newnode();
if(l==r) return ;
uint mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
}
inline uint len(uint l,uint r){ return r-l+1; }
inline uint intersect(uint a,uint b,uint c,uint d){
int x=max(a,c),y=min(b,d);
if(x>y) return 0;
return y-x+1;
}
void add(uint o,uint L,uint R,uint l,uint r){
if(L>r||R<l) return ;
t[o].sum+=intersect(L,R,l,r);
if(l<=L&&R<=r){ t[o].add++; return ; }
uint mid=(L+R)>>1;
if(t[o].lc==0) t[o].lc=newnode();
if(t[o].rc==0) t[o].rc=newnode();
add(t[o].lc,L,mid,l,r);
add(t[o].rc,mid+1,R,l,r);
}
ll query(uint o,uint L,uint R,uint l,uint r,uint add=0){
if(L>r||R<l) return 0;
if(l<=L&&R<=r) return t[o].sum+add*len(L,R);
uint mid=(L+R)>>1;
return query(t[o].lc,L,mid,l,r,add+t[o].add)+query(t[o].rc,mid+1,R,l,r,add+t[o].add);
}
void insert(uint o,uint l,uint r,uint c){
add(tree[o],1,n,l,r);
if(L[o]==R[o]) return ;
uint mid=(L[o]+R[o])>>1;
if(c<=mid) insert(ls,l,r,c);
else insert(rs,l,r,c);
}
uint kth(uint o,uint l,uint r,ll k){
if(L[o]==R[o]) return L[o];
ll rcnt=query(tree[rs],1,n,l,r);
if(rcnt>=k) return kth(rs,l,r,k);
return kth(ls,l,r,k-rcnt);
}
struct B{
int val,id;
inline bool operator<(const B &x)const{ return val<x.val; }
}b[N];
void init(){
sort(b+1,b+1+maxn);
uint i=1,j=1;
while(j<=maxn){
b[i]=b[j];
while(b[i].val==b[j].val&&j<=maxn) q[b[j++].id].c=i;
++i;
}maxn=i-1;
}
using namespace IO;
int main(){
freopen("in.in","r",stdin);
freopen("tmp","w",stdout);
n=gi();m=gi();
for(register uint i=0;i<m;++i){
q[i].opt=gi();
q[i].l=gi();
q[i].r=gi();
q[i].c=gll();
if(q[i].opt==1){ b[++maxn].val=q[i].c; b[maxn].id=i; }
}
init();
build(1,1,maxn);
for(register uint i=0;i<m;++i){
if(q[i].opt==1) insert(1,q[i].l,q[i].r,q[i].c);
else print(b[kth(1,q[i].l,q[i].r,q[i].c)].val);
}
flush();
return 0;
}
```
by hehelego @ 2018-12-06 12:32:54
@[mrsrz](/space/show?uid=6813) 然而我不会bit上二分...如果写多一个log的肯定凉透...
by hehelego @ 2018-12-06 12:33:30
不如写整体二分
by mrsrz @ 2018-12-06 12:34:25