T1标程
```cpp
#include <bits/stdc++.h>
#include <tr1/unordered_map>
#define REP( i , l , r ) for( int i = (l) ; i <= (r) ; i++ )
using namespace std;
inline int _read(){
register int x = 0 , f = 1;
register char ch = getchar();
while( ch > '9' || ch < '0' ) { if( ch == '-' ) f = -1; ch = getchar(); }
while( ch >= '0' && ch <= '9' ){
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int N , M;
const int maxn = 300000 + 5;
const int INF = 0x7f7f7f7f;
int a[maxn] , b[maxn];
int c[maxn] , pos = 0;
int g[maxn] ;
tr1::unordered_map<int , int> _hash;
int main(){
N = _read() , M = _read();
REP( i , 0 , N - 1 ) a[i] = _read();
REP( j , 0 , M - 1 ) b[j] = _read();
REP( i , 0 , N - 1 ) _hash.insert( make_pair(a[i] , i) );
REP( i , 0 , M - 1 )
if( _hash.count(b[i]) ) { c[pos++] = _hash[b[i]]; }
int ans = 1;
REP( i , 0 , N ) g[i] = INF;
REP( i , 0 , pos - 1 ){
int k = lower_bound( g + 1 , g + N + 1 , c[i] ) - g;
g[k] = c[i]; ans = max( ans , k );
}
cout << ans << endl;
return 0;
}
```
by eternal @ 2016-10-04 21:16:24
前排滋瓷！
by winmt @ 2016-10-04 21:16:28
T2
```cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define red(i, a, b) for(int i = (a); i >= (b); i--)
#define LD long double
#define ll long long
#define abs ABS
#define sqr SQR
#define PII pair<int, int>
#define MP make_pair
#define PB push_back
#define FI first
#define SE second
template<typename tn> void read(tn& a) {
tn x = 0, f = 1; char c = getchar();
while(!isdigit(c)) {
if (c == '-') f = -1;
c = getchar();
}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
a = x * f;
}
template<typename tn> void cmax(tn& a, tn b) { if (b > a) a = b; }
template<typename tn> void cmin(tn& a, tn b) { if (b < a) a = b; }
template<typename tn> tn abs(tn a) { return a < 0 ? -a : a; }
template<typename tn> tn sqr(tn a) { return a * a; }
const int N = 110000;
const ll inf = 1000000000ll * 1000000000ll + 10ll;
struct Edge {
int from, to, len, nxt;
}E[N << 1];
int head[N], vis[N];
ll d[N];
struct Node {
int x;
ll dis;
};
bool operator < (Node a, Node b) { return a.dis < b.dis; }
bool operator > (Node a, Node b) { return a.dis > b.dis; }
priority_queue< Node, vector<Node>, greater<Node> > q;
ll h;
int x, y, z, tail = 0;
inline void addEdge(int from, int to, int len) {
E[++tail] = (Edge){from, to, len, head[from]};
head[from] = tail;
}
inline void Dijkstra() {
rep(i, 0, x) d[i] = inf;
d[1 % x] = 1;
q.push((Node){1 % x, d[1 % x]});
while(!q.empty()) {
Node now = q.top();
while(vis[now.x]) {
q.pop();
if (q.empty()) return;
now = q.top();
}
q.pop();
int x = now.x; vis[x] = 1;
for(int i = head[x]; i != -1; i = E[i].nxt) {
int v = E[i].to;
if (vis[v] || d[x] + E[i].len > h) continue;
if (d[x] + E[i].len < d[v]) {
d[v] = d[x] + E[i].len;
q.push((Node){v, d[v]});
}
}
}
}
int main() {
read(h);
read(x); read(y); read(z);
rep(i, 0, x) head[i] = -1;
rep(i, 0, x - 1) {
addEdge(i, (i + y) % x, y);
addEdge(i, (i + z) % x, z);
}
Dijkstra();
ll ans = 0;
rep(i, 0, x - 1) {
if (d[i] > h) continue;
ans += (h - d[i]) / x + 1;
}
cout << ans << endl;
return 0;
}
```
by eternal @ 2016-10-04 21:17:01
T3
```cpp
#include <bits/stdc++.h>
#define REP( i , l , r ) for( int i = (l) ; i <= (r) ; i++ )
using namespace std;
typedef long long ll;
inline int _read(){
int x = 0;
char ch = getchar();
while( ch < '0' || ch > '9' ) ch = getchar();
while( ch >='0' && ch <='9' ){
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
const int MOD = 1e9 + 9;
const int maxn = 300000;
ll bas = 276601605 , q1 = 691504013 , q2 = 308495997;
ll mul1[maxn] , mul2[maxn] , s[maxn];
int c[maxn] , N , K ;
struct node{
ll a , b ;
ll sum;
} t[maxn * 4];
void prework( int M ){
mul1[0] = mul2[0] = 1;
REP( i , 1 , M ){
mul1[i] = mul1[i - 1] * q1 % MOD;
mul2[i] = mul2[i - 1] * q2 % MOD;
}
}
void build( int x , int l , int r ){
t[x].a = t[x].b = t[x].sum = 0;
if( l == r ) return;
int mid = ( l + r ) >> 1;
build( x << 1 , l , mid );
build( (x << 1) + 1 , mid + 1 , r );
}
void push_down( int x , int l , int r ){
ll aa = t[x].a , bb = t[x].b;
if( 0 == aa && 0 == bb ) return;
int lc = x << 1 , rc = (x << 1) | 1 , mid = (l + r) >> 1;
int l1 = mid - l + 1 , l2 = r - mid;
t[lc].a = (t[lc].a + aa) % MOD;
t[lc].b = (t[lc].b + bb) % MOD;
t[lc].sum = ( t[lc].sum + aa * (mul1[l1 + 2] - mul1[2]) ) % MOD;
t[lc].sum = ( t[lc].sum - bb * (mul2[l1 + 2] - mul2[2]) ) % MOD;
t[rc].a = ( t[rc].a + aa * mul1[l1] ) % MOD;
t[rc].b = ( t[rc].b + bb * mul2[l1] ) % MOD;
t[rc].sum = ( t[rc].sum + aa * mul1[l1] % MOD * (mul1[l2 + 2] - mul1[2] ) % MOD ) % MOD;
t[rc].sum = ( t[rc].sum - bb * mul2[l1] % MOD * (mul2[l2 + 2] - mul2[2] ) % MOD ) % MOD;
t[x].a = t[x].b = 0;
}
void push_up( int x ){
t[x].sum = ( t[x << 1].sum + t[(x << 1) + 1].sum ) % MOD;
}
ll query( int x , int l , int r , int ql , int qr ){
if( l == ql && r == qr ) return t[x].sum;
push_down( x , l , r );
int mid = (l + r) >> 1;
if( qr <= mid ) return query( x << 1 , l , mid , ql , qr );
else if( ql > mid ) return query( (x << 1) | 1 , mid + 1 , r , ql , qr );
else return (query( x << 1 , l , mid , ql , mid ) + query( (x << 1) | 1 , mid + 1 , r , mid + 1 , qr )) % MOD;
}
void update( int rt , int l , int r , int ql , int qr , ll x , ll y ){
if( l == ql && r == qr ){
int len = r - l + 1;
t[rt].a = (t[rt].a + x) % MOD;
t[rt].b = (t[rt].b + y) % MOD;
t[rt].sum = ( t[rt].sum + x * (mul1[len + 2] - mul1[2]) ) % MOD;
t[rt].sum = ( t[rt].sum - y * (mul2[len + 2] - mul2[2]) ) % MOD;
return;
}
push_down( rt , l , r );
int mid = (l + r) >> 1;
if( qr <= mid ) update( (rt << 1) , l , mid , ql , qr , x , y );
else if( ql > mid ) update( (rt << 1) | 1 , mid + 1 , r , ql , qr , x , y );
else{
int len = mid - ql + 1;
update( rt << 1 , l , mid , ql , mid , x , y );
update( (rt << 1) | 1 , mid + 1 , r , mid + 1 , qr , x * mul1[len] % MOD , y * mul2[len] % MOD );
}
push_up( rt );
}
int main(){
N = _read() , K = _read();
REP( i , 1 , N ){
c[i] = _read();
s[i] = s[i - 1] + c[i];
}
prework( 60200 );
build( 1 , 1 , N );
REP( i , 1 , K ){
int opt , l , r;
opt = _read() , l = _read() , r = _read();
if( opt == 1 ) update( 1 , 1 , N , l , r , 1 , 1 );
else{
ll ret = ( bas * query( 1 , 1 , N , l , r ) % MOD + s[r] - s[l - 1] ) % MOD;
if( ret < 0 ) ret += MOD;
printf( "%lld\n" , ret );
}
}
return 0;
}
```
by eternal @ 2016-10-04 21:17:45
T3NO2
```cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define red(i, a, b) for(int i = (a); i >= (b); i--)
#define LD long double
#define ll long long
#define abs ABS
#define sqr SQR
#define PII pair<int, int>
#define MP make_pair
#define PB push_back
#define FI first
#define SE second
template<typename tn> void read(tn& a) {
tn x = 0, f = 1; char c = getchar();
while(!isdigit(c)) {
if (c == '-') f = -1;
c = getchar();
}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
a = x * f;
}
template<typename tn> void cmax(tn& a, tn b) { if (b > a) a = b; }
template<typename tn> void cmin(tn& a, tn b) { if (b < a) a = b; }
template<typename tn> tn abs(tn a) { return a < 0 ? -a : a; }
template<typename tn> tn sqr(tn a) { return a * a; }
const int N = 110000;
const ll mod = 1000000009;
struct Node {
int l, r;
ll sum, f1, f2;
}t[N * 4];
int n, m;
ll a[N], F[N];
void Build(int x, int l, int r) {
int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
t[x].l = l; t[x].r = r;
t[x].f1 = t[x].f2 = 0;
if (l == r) {
t[x].sum = a[l];
return;
}
Build(lc, l, mid); Build(rc, mid + 1, r);
t[x].sum = (t[lc].sum + t[rc].sum) % mod;
}
inline ll getH(ll a, ll b, ll n) {
if (n == 1) return a;
if (n == 2) return b;
return (a * F[n - 2] % mod + b * F[n - 1] % mod) % mod;
}
inline ll SUM(ll a, ll b, ll n) {
if (n == 1) return a;
if (n == 2) return (a + b) % mod;
return (getH(a, b, n + 2) - b + mod) % mod;
}
void pushdown(int x) {
int l = t[x].l, r = t[x].r;
int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
(t[lc].f1 += t[x].f1) %= mod;
(t[lc].f2 += t[x].f2) %= mod;
(t[lc].sum += SUM(t[x].f1, t[x].f2, mid - l + 1)) %= mod;
(t[rc].f1 += getH(t[x].f1, t[x].f2, mid - l + 2)) %= mod;
(t[rc].f2 += getH(t[x].f1, t[x].f2, mid - l + 3)) %= mod;
t[rc].sum += SUM(t[x].f1, t[x].f2, r - l + 1) - SUM(t[x].f1, t[x].f2, mid - l + 1);
(t[rc].sum += mod) %= mod;
t[x].f1 = t[x].f2 = 0;
}
void update(int x, int l, int r, int ql, int qr) {
int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
if (ql <= l && r <= qr) {
(t[x].f1 += F[l - ql + 1]) %= mod;
(t[x].f2 += F[l - ql + 2]) %= mod;
(t[x].sum += SUM(F[l - ql + 1], F[l - ql + 2], r - l + 1)) %= mod;
return;
}
pushdown(x);
if (ql <= mid) update(lc, l, mid, ql, qr);
if (qr > mid) update(rc, mid + 1, r, ql, qr);
t[x].sum = (t[lc].sum + t[rc].sum) % mod;
return;
}
ll query(int x, int l, int r, int ql, int qr) {
int mid = (l + r) >> 1, lc = x << 1, rc = lc + 1;
if (ql <= l && r <= qr) return t[x].sum;
pushdown(x);
if (qr <= mid) return query(lc, l, mid, ql, qr);
else if (ql > mid) return query(rc, mid + 1, r, ql, qr);
else return (query(lc, l, mid, ql, qr) + query(rc, mid + 1, r, ql, qr)) % mod;
}
int main() {
read(n); read(m);
rep(i, 1, n) read(a[i]);
F[1] = F[2] = 1;
rep(i, 3, n + 10) F[i] = (F[i - 1] + F[i - 2]) % mod;
Build(1, 1, n);
rep(i, 1, m) {
int tp, l, r;
read(tp); read(l); read(r);
if (tp == 1) update(1, 1, n, l, r);
else printf("%lld\n", query(1, 1, n, l, r));
}
return 0;
}
```
by eternal @ 2016-10-04 21:26:00
根本看不懂（我是学pascal）
by wowwow @ 2016-10-04 22:06:11
```cpp
pas No1const
maxn=300000;
var
n,m,i,j,all,t,ans:longint;
a,b,e,f,g:array[1..maxn] of longint;
hash:array[1..maxn*2] of longint;
c,d:array[1..maxn*2] of longint;
function func(x:longint):longint;
var
l,r,mid:longint;
begin
if ans=0
then exit(0);
l:=0;r:=ans;
while l<r do
begin
mid:=(l+r+1) div 2;
if x>=g[mid]
then l:=mid
else r:=mid-1;
end;
exit(l);
end;
function max(x,y:longint):longint;
begin
```
if x>y
```cpp
then exit(x)
else exit(y);
end;
procedure sort(l,r:longint);
var
i,j,x,y:longint;
begin
i:=l;
j:=r;
x:=c[(l+r) div 2];
repeat
while c[i]<x do
inc(i);
while x<c[j] do
dec(j);
if not(i>j)
then begin
y:=c[i];
c[i]:=c[j];
c[j]:=y;
y:=d[i];
d[i]:=d[j];
d[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j
then sort(l,j);
if i<r
then sort(i,r);
end;
begin
read(n,m);
for i:=1 to n do
begin
read(a[i]);
c[i]:=a[i];
d[i]:=i;
end;
for i:=1 to m do
begin
read(b[i]);
c[i+n]:=b[i];
d[i+n]:=i+n;
end;
sort(1,n+m);
all:=0;
for i:=1 to n+m do
begin
if (i=1)or(c[i]<>c[i-1])
then inc(all);
if d[i]<=n
then a[d[i]]:=all
else b[d[i]-n]:=all;
end;
for i:=1 to n do
hash[a[i]]:=i;
for i:=1 to m do
if hash[b[i]]<>0
then e[hash[b[i]]]:=i;
ans:=0;
for i:=1 to n do
begin
if e[i]=0
then continue;
t:=func(e[i])+1;
f[i]:=t;
```
if t>ans
```cpp
then ans:=t;
if (g[t]=0)or(e[i]<g[t])
then g[t]:=e[i];
end;
writeln(ans);
end.
```
by eternal @ 2016-10-04 22:25:52
pas T2
```cpp
const
maxv=100000;
maxq=10000000;
var
n,ans,x,y,z,t,m,l,r:int64;
i:longint;
a,b:array[0..maxv] of int64;
q:array[1..maxq] of int64;
procedure func(var x,y,z:int64);
var
t:int64;
begin
if x>y then begin t:=x;x:=y;y:=t;end;
if y>z then begin t:=y;y:=z;z:=t;end;
if x>y then begin t:=x;x:=y;y:=t;end;
end;
begin
read(n,x,y,z);
func(x,y,z);
if x=1
then begin writeln(n);exit;end;
l:=1;r:=1;
a[1]:=1;
b[1]:=1;
q[1]:=1;
while not((l=r+1)or(r=maxq)and(l=1)) do
begin
if b[q[l]]=1
then begin
t:=a[q[l]]+y;
m:=t mod x;
if (t<=n)and((a[m]=0)or(a[m]>t))
then begin
a[m]:=t;
inc(b[m]);
inc(r);
```
if r>maxq
```cpp
then r:=1;
q[r]:=m;
end;
t:=a[q[l]]+z;
m:=t mod x;
if (t<=n)and((a[m]=0)or(a[m]>t))
then begin
a[m]:=t;
inc(b[m]);
inc(r);
```
if r>maxq
```cpp
then r:=1;
q[r]:=m;
end;
end;
dec(b[q[l]]);
inc(l);
```
if l>maxq
```cpp
then l:=1;
end;
for i:=0 to x-1 do
if a[i]<>0
then inc(ans,(n-a[i]) div x+1);
writeln(ans);
end.
```
by eternal @ 2016-10-04 22:26:35
pas T3
```cpp
const
v=1000000009;
maxn=100000;
type
node=record
lc:longint;
rc:longint;
t1:int64;
t2:int64;
sum:int64;
end;
var
n,m,i,c,l,r,all:longint;
x,f,s:array[0..maxn] of int64;
a:array[1..maxn*2] of node;
function cal(x,y,z:int64):int64;
var
sa,sb:int64;
begin
if z=2
then exit(x+y);
sa:=f[z];
sb:=s[z-1];
exit((sa*x+sb*y) mod v);
end;
function get(x,y,z:int64):int64;
begin
exit((x*f[z-2]+y*f[z-1]) mod v);
end;
procedure pushdown(i,l,r:longint);
var
mid,x,y:longint;
t1,t2:int64;
begin
mid:=(l+r) div 2;
x:=a[i].lc;y:=a[i].rc;
a[x].t1:=(a[x].t1+a[i].t1) mod v;
a[x].t2:=(a[x].t2+a[i].t2) mod v;
a[x].sum:=(a[x].sum+cal(a[i].t1,a[i].t2,mid-l+1)) mod v;
t1:=get(a[i].t1,a[i].t2,mid-l+2);
t2:=get(a[i].t1,a[i].t2,mid-l+3);
a[y].t1:=(a[y].t1+t1) mod v;
a[y].t2:=(a[y].t2+t2) mod v;
a[y].sum:=(a[y].sum+cal(t1,t2,r-mid)) mod v;
a[i].t1:=0;
a[i].t2:=0;
end;
procedure maintain(i,l,r,ql,qr:longint;t1,t2:int64);
var
mid:longint;
begin
if l=r
then begin
a[i].sum:=(a[i].sum+t1) mod v;
exit;
end;
if (l=ql)and(r=qr)
then begin
a[i].t1:=(a[i].t1+t1) mod v;
a[i].t2:=(a[i].t2+t2) mod v;
a[i].sum:=(a[i].sum+cal(t1,t2,r-l+1)) mod v;
exit;
end;
mid:=(l+r) div 2;
a[i].sum:=(a[i].sum+cal(t1,t2,qr-ql+1)) mod v;
pushdown(i,l,r);
if qr<=mid
then maintain(a[i].lc,l,mid,ql,qr,t1,t2)
else if ql>mid
then maintain(a[i].rc,mid+1,r,ql,qr,t1,t2)
else begin
maintain(a[i].lc,l,mid,ql,mid,t1,t2);
maintain(a[i].rc,mid+1,r,mid+1,qr,get(t1,t2,mid-ql+2),get(t1,t2,mid-ql+3));
end;
end;
procedure build(i,l,r:longint);
var
mid:longint;
begin
if l=r
then begin
a[i].sum:=x[l];
exit;
end;
mid:=(l+r) div 2;
inc(all);
a[i].lc:=all;
build(all,l,mid);
inc(all);
a[i].rc:=all;
build(all,mid+1,r);
a[i].sum:=(a[a[i].lc].sum+a[a[i].rc].sum) mod v;
end;
function query(i,l,r,ql,qr:longint):longint;
var
mid:longint;
begin
if (l=ql)and(r=qr)
then exit(a[i].sum);
mid:=(l+r) div 2;
pushdown(i,l,r);
if qr<=mid
then exit(query(a[i].lc,l,mid,ql,qr))
else if ql>mid
then exit(query(a[i].rc,mid+1,r,ql,qr))
else exit((query(a[i].lc,l,mid,ql,mid)+query(a[i].rc,mid+1,r,mid+1,qr)) mod v);
end;
begin
read(n,m);
for i:=1 to n do
read(x[i]);
f[1]:=1;
f[2]:=1;
for i:=3 to n do
f[i]:=(f[i-1]+f[i-2]) mod v;
s[1]:=f[1];
for i:=2 to n do
s[i]:=(s[i-1]+f[i]) mod v;
all:=1;
build(1,1,n);
for i:=1 to m do
begin
read(c,l,r);
case c of
1:maintain(1,1,n,l,r,1,1);
2:writeln(query(1,1,n,l,r));
end;
end;
end.
```
by eternal @ 2016-10-04 22:27:11
##这.........
by wowwow @ 2016-10-05 11:06:06