网址：代码部落
密码 666888（所有CSP-J/S比赛密码）
一： T1 做法： 二次差分
二： T2 吉祥区间
思路：主要是倍增，处理ST表 ，f[i][j]表示以i为起点，往右延2^j次幂区间里面的
吉祥区间的个数，通过f数组就log2N的复杂度求解区间[l,r]里面的吉祥区间个数
番外：一开始我的思路正确，但在代码时，把倍增打炸了，在计算过程中超过了范围，
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,q,a[N],f[N][21];
void solve(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int j=1;
unordered_map<int,int> st;
for(int i=1;i<=n;i++){
while(j<=n&&st.size()<8){
st[a[j]]++,j++;
}
if(j==n+1&&st.size()<8)break;
f[i][0]=j-1;
st[a[i]]--;
if(!st[a[i]]) st.erase(a[i]);
}
for(int j=1;j<=20;j++){
for(int i=1;i<=n;i++){
if(f[i][j-1]!=0){
f[i][j]=f[f[i][j-1]+1][j-1];
}
}
}
for(int i=1;i<=q;i++){
int l,r,ans=0;
cin>>l>>r;
for(int j=20;j>=0;j--){
if(f[l][j]!=0&&r>=f[l][j]){
l=f[l][j]+1;
ans+=1<<j;
}
}
cout<<ans<<endl;
}
}
signed main(){
solve();
return 0;
}三：黑白的交替整数
首先观察黑白交替数的数量：
二位数有9*5个交替 三位数有9*5*5个交替数 n位数有9*5^(n-1)个交替数
可以在1~10^18里面进行二分，查看1~mid里面的交替数的数量是否大于n，
满足左移，不满足右移，从而定位第n位的交替数
问题转化为给定数x 如何寻找1~x里面有多少个交替数，定义f（x,-1）函数
处理1~x 有多少个交替数，第二个参数是对最高位的约束，-1 是无，0表示必须为偶数，1表示必须为 奇数， 时间复杂度：O(2^log10n)
特殊： 当最高位是奇数，只有4*5^(n-1）种可能性，
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=25;
int n;
ll n10[N],n5[N];
int glen(ll n){
int l=0;
while(n){
n/=10;
l++;
}
return l;
}
ll cal(ll n,int len,int x){
if(len<1) return 0;
if(len==1){
if(x==-1) return 0;
int t=0;
for(int i=0;i<=n;i++){
if(i%2==x) t++;
}
return t;
}
int h=n/n10[len-1];
if(x==-1){
ll res=(h-1)*n5[len-1];
res+=cal(n10[len-1]-1,len-1,-1);
res+=cal(n%n10[len-1],len-1,1-h%2);
return res;
}
else{
ll res=0;
for(int i=0;i<h;i++){
if(i%2==x){
res+=n5[len-1];
}
}
if(h%2==x){
res+=cal(n%n10[len-1],len-1,1-h%2);
}
return res;
}
}
int main(){
n10[0]=n5[0]=1;
for(int i=1;i<=18;i++){
n10[i]=n10[i-1]*10;
n5[i]=n5[i-1]*5;
}
ll n;
cin>>n;
ll l=1,r=1e18;
while(l<=r){
ll mid=l+r>>1;
if(cal(mid,glen(mid),-1)>=n){
r=mid-1;
}
else {
l=mid+1;
}
}
cout<<l<<endl;
return 0;
}四： 黑白的矩形网格：
注意到涂格子的方式，可以表示为写上长度为n,m的01串x,y
对应某格子的颜色为cij=xi XOR yj ，无限制情况下，01串可任取，总方案数为
2^(n+m-1) 同时，我们将颜色转化：
1.若c[i][j]=0,有xi==yj
2. 若c[i][j]=1 有xi!=yj.
没有限制的位置可以任意填0,1 离散化成图，若一连通块不冲突，则有2种
否则答案为0，时间复杂度O（n log n）;
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const ll mod=998244353;
const int N=3e5+10;
struct node{
int x,y,c;
bool operator< (const node &nd)const{
if(x!=nd.x) return x<nd.x;
if(y!=nd.y) return y<nd.y;
return c<nd.c;
}
bool operator==(const node &nd) const{
return x==nd.x&&y==nd.y&&c==nd.c;
}
}a[N];
int n,m,k,xx[N],yy[N];
vector<pii> ve[2*N];
bool vis[2*N];
int val[2*N];
ll qpow(ll a,ll n){
ll r=1;
while(n){
if(n&1) r=r*a%mod;
a=a*a%mod;
n>>=1;
}
return r;
}
bool dfs(int u){
vis[u]=1;
for(pii &p: ve[u]){
int &v=p.first,&w=p.second;
if(vis[v]){
if((val[u]^w)!=val[v]){
return 0;
}
continue;
}
val[v]=val[u]^w;
if(!dfs(v)) return 0;
}
return 1;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=k;i++){
cin>>a[i].x>>a[i].y>>a[i].c;
xx[i]=a[i].x;
yy[i]=a[i].y;
}
sort(a+1,a+k+1);
sort(xx+1,xx+k+1);
sort(yy+1,yy+k+1);
int kk,nn,mm;
kk=unique(a+1,a+k+1)-(a+1);
nn=unique(xx+1,xx+k+1)-(xx+1);
mm=unique(yy+1,yy+k+1)-(yy+1);
for(int i=1;i<=kk;i++){
a[i].x=lower_bound(xx+1,xx+nn+1,a[i].x)-xx;
a[i].y=lower_bound(yy+1,yy+mm+1,a[i].y)-yy;
ve[a[i].x].push_back(pii(a[i].y+nn,a[i].c));
ve[a[i].y+nn].push_back(pii(a[i].x,a[i].c));
}
int cnt=n+m-nn-mm;
for(int i=1;i<=nn+mm;i++){
if(vis[i]) continue;
if(dfs(i)) cnt++;
else {
cout<<0<<endl;
return 0;
}
}
cout<<qpow(2,cnt-1)<<endl;
}